Hướng dẫn giải của Educational Backtracking: Điền chữ L
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lời giải: Duyệt trâu. Giả sử đang có bảng hiện tại, với một số hình đã được thêm vào. Duyệt qua từng cặp hình sẽ dùng tiếp theo, vị trí có thể đặt. Bảng 16 ô nhưng với mỗi hình chỉ có tối đa 9 vị trí có thể đặt nên số khả năng đặt hình là 9 + 9 = 18. Mặt khác độ sâu backtrack ~\leq~ số hình cần đặt ~\leq \lfloor 16 / 3 \lfloor = 5~ nên độ phức tạp duyệt trâu là ~18^5* nm~.
Code C++:
#include<bits/stdc++.h>
using namespace std;
const int max_len = 17;
int n, m;
int grid[max_len][max_len];
void check_all_filled() {
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(!grid[i][j]) return;
}
}
cout << "YES" << endl;
exit(0);
}
void backtrack() {
check_all_filled();
int opt_count = 0;
for(int i = 0; i + 1 < n; i++) {
for(int j = 0; j + 1 < m; j++) {
opt_count += 2;
assert(opt_count <= 18);
if(grid[i][j] == 0 && grid[i + 1][j] == 0 && grid[i + 1][j + 1] == 0) {
grid[i][j] = grid[i + 1][j] = grid[i + 1][j + 1] = 1;
backtrack();
grid[i][j] = grid[i + 1][j] = grid[i + 1][j + 1] = 0;
}
if(grid[i][j + 1] == 0 && grid[i + 1][j] == 0 && grid[i + 1][j + 1] == 0) {
grid[i][j + 1] = grid[i + 1][j] = grid[i + 1][j + 1] = 1;
backtrack();
grid[i][j + 1] = grid[i + 1][j] = grid[i + 1][j + 1] = 0;
}
}
}
}
signed main() {
cin >> n >> m;
int empty = 0;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
char c;
cin >> c;
if(c == '.') {
empty++;
}
else {
grid[i][j] = 1;
}
}
}
backtrack();
cout << "NO" << endl;
}
Bình luận