ALADDIN - Aladdin
Tác giả: hieult
Ngôn ngữ: C++
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<list>
//#include<conio.h>
#define ep 0.000000001
#define maxn 222
#define oo 1111111111
#define base 100000000
#define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
double const PI=4*atan(1);
using namespace std;
typedef pair<int, int> II;
typedef vector<int> VI;
typedef vector<II> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;
int n,a[maxn][maxn],c[maxn][maxn],tong;
inline int sum(int u, int v){
return a[u][v]+a[u][v+1]+
a[u+1][v]+a[u+1][v+1];
}
bool TRY(int u,int v){
int t=0,uu=0,vv=0;
//printf("%d %d\n",u,v);
if(u==n || v==1){
if(u+v>=n) { vv = n; uu = u+v+1-vv;}
else { uu = 1; vv= u+v+1-uu;}
}
else{ uu = u+1; vv = v-1;}
if(u==n && v== n){
// printf("DDDDD\n");
a[u][v] = 0;
t = c[u-1][v-1]-sum(u-1,v-1);
if(t<0 || t>1) return false;
a[u][v] = t; return true;
}
if(u==1){
a[u][v] = 0; if(TRY(uu,vv)) return true;
a[u][v] = 1; if(TRY(uu,vv)) return true;
return false;
}
if(v==1){
a[u][v] = 0; if(TRY(uu,vv)) return true;
a[u][v] = 1; if(TRY(uu,vv)) return true;
return false;
}
a[u][v] = 0; t = c[u-1][v-1]-sum(u-1,v-1);
if(t<0 || t>1) return false;
a[u][v] = t;
// if(u==n && sum(u,v-1)!=c[u][v-1]) return false;
// if(v==n && sum(u-1,v)!=c[u-1][v]) return false;
if(TRY(uu,vv)) return true;
return false;
}
int main(){
// freopen("ALADIN.in","r",stdin);
scanf("%d",&n);
for(int i = 1;i<n;i++) for(int j = 1;j<n;j++) scanf("%d",&c[i][j]);
memset(a,0,sizeof(a));
// tong = 3;
bool flag = false;
for(int i = 0;i<=1;i++) { a[1][1] = i; if(TRY(1,2)){flag = true; break;}}
if(!flag) printf("No solution");
else{
for(int i = 1;i<=n;i++) for(int j = 1;j<=n;j++)
printf("%d%c",a[i][j],j<n?' ':'\n');
}
// getch();
}