Editorial for Educational Backtracking: Điền chữ L
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
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;
}
Comments