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;
}

Download