ALADDIN - Aladdin
Tác giả: ladpro98
Ngôn ngữ: C++
#include <iostream>
#include <cstdio>
#include <algorithm>
const int MAXN = 222;
const int dx[4] = {0,0,1,1};
const int dy[4] = {0,1,0,1};
using namespace std;
int a[MAXN][MAXN], black[MAXN][MAXN];
int n;
bool found;
bool inBound(int x, int y) {
return (0<x)&&(x<=n)&&(0<y)&&(y<=n);
}
bool ok(int x, int y, int l, int r) {
if (!inBound(x,y)) return true;
if ((x==n)||(y==n)) return true;
int i,p,q;
int t = a[x][y];
for(i=0; i<4; i++) {
p = x+dx[i];
q = y+dy[i];
if ((inBound(p,q))&&(black[p][q])) t--;
}
return (l<=t)&&(t<=r);
}
void BackTrack(int p, int q, int ii, int jj) {
if (found) return;
int i,j,v;
if (p>n) {
found = true;
for(i=1; i<=n; i++) {
for(j=1; j<=n; j++)
printf("%d ", black[i][j]);
printf("\n");
}
return;
}
for(v=0; v<=1; v++) {
black[ii][jj] = v;
if (!ok(ii-1,jj-1,0,0)) continue;
if (!ok(ii-1,jj,0,1)) continue;
if (!ok(ii,jj-1,0,2)) continue;
i = ii+1; j=jj-1;
if (inBound(i,j))
BackTrack(p,q,i,j);
else {
if (q<n) BackTrack(p,q+1,p,q+1);
else BackTrack(p+1,q,p+1,q);
}
}
black[ii][jj] = 0;
}
int main()
{
//freopen("ALADDIN.in", "r", stdin);
scanf("%d", &n);
int i,j;
for(i=1; i<n; i++) for(j=1; j<n; j++) scanf("%d", &a[i][j]);
BackTrack(1,1,1,1);
if (!found) printf("No solution");
return 0;
}