NKMINES - Trò chơi dò mìn
Tác giả: khuc_tuan
Ngôn ngữ: C++
#include <iostream>
using namespace std;
int m, n;
int a[222][222];
int b[222][222], bluu[222][222];
bool daxong;
bool inside( int i,int j) {
return (i>=0) && (i<m) && (j>=0) && (j<n);
}
int check(int i,int j) {
int total = a[i][j];
for(int di=-1;di<=1;++di) for(int dj=-1;dj<=1;++dj) if(di!=0 || dj!=0) {
int x = i + di;
int y = j + dj;
if(inside( x, y)) total -= b[x][y];
}
return total;
}
bool process(int i) {
for(int j=1;j<i;++j) if(inside(i,j)) {
b[i][j] = 0;
int t = check( i-1, j-1);
if(t!=0 && t!=1) return false;
b[i][j] = t;
}
for(int j=1;j<i;++j) if(inside(j,i)) {
b[j][i] = 0;
int t = check( j-1, i-1);
if(t!=0 && t!=1) return false;
b[j][i] = t;
}
if(inside(i,i)) {
b[i][i] = 0;
int t = check(i-1,i-1);
if(t!=0 && t!=1) return false;
b[i][i] = t;
}
return true;
}
//int dem = 0;
void duyet(int i) {
if(daxong) return;
if(i>=m && i>=n) {
//++dem;
bool ok = true;
for(int j=0;j<m;++j) if(check(j,n-1)!=0) {
//if(dem==2) cout << j << " " << n-1 << " " << check(j,n-1) << " " << a[j][n-1] << endl;
ok = false;
break;
}
for(int j=0;j<n;++j) if(check(m-1,j)!=0) {
//if(dem==2) cout << m-1 << " " << j << " " << check(m-1,j) << " " << a[m-1][j] << endl;
ok = false;
break;
}
if(!ok) return;
daxong = true;
//for(int i=0;i<m;++i) { for(int j=0;j<n;++j) printf("%d ", b[i][j]); puts(""); }
//puts("");
//cout << check(0, 3) << " " << a[0][3] << endl << endl;
memmove( bluu, b, sizeof(b));
return;
}
if(i==0) {
b[0][0] = 0;
duyet(i+1);
b[0][0] = 1;
duyet(i+1);
return;
}
for(b[i][0]=0;b[i][0]<2;++b[i][0]) for(b[0][i]=0;b[0][i]<2;++b[0][i]) {
bool ok = process(i);
if(ok) duyet(i+1);
}
}
int main() {
scanf("%d%d", &m, &n);
for(int i=0;i<m;++i) for(int j=0;j<n;++j) scanf("%d", &a[i][j]);
daxong = false;
duyet(0);
for(int i=0;i<m;++i) { for(int j=0;j<n;++j) printf("%d ", bluu[i][j]); printf("\n"); }
//system("pause");
return 0;
}