Ở mỗi ô ta có 2 trạng thái là đặt bomb hoặc không đặt bomb. Ta sẽ thử hết tất cả các trường hợp có thể xảy ra với độ phức tạp n x m x 2^(n x m).
Để tối ưu hơn, ta áp dụng kĩ thuật nhánh và cận. Ở đây mình đệ quy theo thứ tự từ trái sang phải và từ trên xuống dưới cho dễ làm.
Ở ô (i, j), ta sẽ kiểm tra các ô (0, 1, ..., m-1) của hàng (i - 2) xem có thỏa mãn input đề bài hay không.
Tiếp đến, ta sẽ kiểm tra các ô (0, 1, ..., j - 2) của hàng (i - 1) xem có thỏa mãn input đề bài hay không.
Ở đây hàm count(x, y) dùng để đếm số bom xung quanh ô (x, y)
#include <bits/stdc++.h>
using namespace std;
const int N = 25;
int dx[] = { -1, 0, 1, -1, 1, -1, 0, 1};
int dy[] = { -1, -1, -1, 0, 0, 1, 1, 1};
int n, m;
int a[N][N], grid[N][N];
int count(int x, int y) {
int res = 0;
for (int i = 0; i < 8; ++i) {
int u = x + dx[i], v = y + dy[i];
if (u >= 0 && v >= 0 && u < n && v < m) {
res += grid[u][v];
}
}
return res;
}
bool notPossible(int i, int j) {
if (i > 1) {
for (int y = 0; y < m; ++y) {
if (count(i - 2, y) != a[i - 2][y]) return true;
}
}
if (i > 0) {
for (int y = 0; y + 1 < j; ++y) {
if (count(i - 1, y) != a[i - 1][y]) return true;
}
}
return false;
}
void print_grid() {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cout << grid[i][j] << ' ';
}
cout << '\n';
}
}
bool dfs(int i, int j) {
if (i == n) {
for (int x = 0; x < n; ++x) {
for (int y = 0; y < m; ++y) {
if (count(x, y) != a[x][y]) return false;
}
}
return true;
}
if (notPossible(i, j)) return false;
int u = i + (j + 1) / m, v = (j + 1) % m;
for (int k = 1; k >= 0; --k) {
grid[i][j] = k;
if (dfs(u, v)) return true;
}
return false;
}
void solve() {
cin >> n >> m;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> a[i][j];
}
}
if (dfs(0, 0)) print_grid();
}
marcus06
Created at
27 likes