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

Download