Editorial for Aladdin
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của flashmt
uses math; const fi=''; maxn=210; type ar=array[1..maxn,1..maxn] of longint; var n:longint; a,b:ar; qx,qy:array[0..maxn*maxn] of longint; procedure rf; var i,j,dem:longint; begin read(n); for i:=1 to n-1 do for j:=1 to n-1 do read(b[i,j]); qx[1]:=1; qy[1]:=1; dem:=1; for i:=3 to n+n do for j:=max(1,i-n) to min(n,i-1) do begin inc(dem); qx[dem]:=j; qy[dem]:=i-j; end; end; procedure wf; var i,j:longint; begin for i:=1 to n do begin for j:=1 to n do write(a[i,j],' '); writeln; end; halt; end; procedure edit(x,y,val:longint); begin if x>1 then b[x-1,y]:=b[x-1,y]+val; if y>1 then b[x,y-1]:=b[x,y-1]+val; b[x,y]:=b[x,y]+val; end; procedure att(p:longint); var i,j,x,y,xx,yy:longint; c0,c1:boolean; begin if p>n*n then wf; x:=qx[p]; y:=qy[p]; c0:=true; c1:=true; if (x>1) and (y>1) then begin if b[x-1,y-1]<>0 then c0:=false; if b[x-1,y-1]<>1 then c1:=false; end; if c0 then begin a[x,y]:=0; att(p+1); end; if c1 then begin a[x,y]:=1; edit(x,y,-1); att(p+1); edit(x,y,1); end; end; procedure pr; begin att(1); writeln('No solution'); end; begin assign(input,fi); reset(input); rf; pr; close(input); end.
Code mẫu của ladpro98
#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; }
Code mẫu của RR
{$R+,Q+} uses math; const FINP=''; FOUT=''; MAXN=401; var f1,f2:text; test,t,n:longint; a,sl:array[1..MAXN,1..MAXN] of longint; ok:boolean; procedure openF; begin assign(f1,FINP); reset(f1); assign(f2,FOUT); rewrite(f2); end; procedure closeF; begin close(f1); close(f2); end; procedure inp; var i,j:longint; begin read(f1,n); for i:=1 to n-1 do for j:=1 to n-1 do read(f1,sl[i,j]); end; procedure ans; var i,j:longint; begin for i:=1 to n do begin for j:=1 to n do write(f2,a[i,j],' '); writeln(f2); end; closeF; halt; end; procedure dienSo(u:longint); var i,j,count:longint; begin ok:=true; for i:=2 to n do begin j:=u+1-i; if (j<2) or (j>n) then continue; count:=a[i-1,j-1]+a[i-1,j]+a[i,j-1]; if count=sl[i-1,j-1] then a[i,j]:=0 else if count+1=sl[i-1,j-1] then a[i,j]:=1 else ok:=false; end; end; procedure xoaSo(u:longint); var i,j:longint; begin for i:=2 to n do begin j:=u+1-i; if (j<2) then continue; a[i,j]:=0; end; end; procedure try(u:longint); var i,j:longint; begin for i:=0 to 1 do if (u<=n) or (i=0) then for j:=0 to 1 do if (u<=n) or (j=0) then begin a[1,u]:=i; a[u,1]:=j; dienSo(u); if ok then begin if u=n+n then ans else try(u+1) end; xoaSo(u); a[1,u]:=0; a[u,1]:=0; end; end; procedure solve; begin a[1,1]:=0; try(2); a[1,1]:=1; try(2); end; begin openF; inp; solve; writeln(f2,'No solution'); closeF; end.
Code mẫu của hieult
#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(); }
Code mẫu của khuc_tuan
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int[][] res; public static void main(String[] args) throws Exception { BufferedReader kb = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(kb.readLine()); int[][] sum = new int[n - 1][n - 1]; for (int i = 0; i + 1 < n; ++i) { StringTokenizer st = new StringTokenizer(kb.readLine()); for (int j = 0; j + 1 < n; ++j) sum[i][j] = Integer.parseInt(st.nextToken()); } int[][] a = new int[n][n]; res = null; go(0, sum, a); if (res == null) System.out.println("No solution"); else for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) System.out.print(res[i][j] + " "); System.out.println(); } } static void go(int pos, int[][] sum, int[][] a) { if (res != null) return; int n = a.length; if (pos >= n) { res = new int[n][]; for (int i = 0; i < n; ++i) res[i] = a[i].clone(); return; } if (pos == 0) { a[0][0] = 0; go(pos + 1, sum, a); a[0][0] = 1; go(pos + 1, sum, a); return; } for (a[0][pos] = 0; a[0][pos] <= 1; ++a[0][pos]) { for (a[pos][0] = 0; a[pos][0] <= 1; ++a[pos][0]) { boolean ok = true; for (int i = 1; i <= pos; ++i) { a[i][pos] = sum[i - 1][pos - 1] - a[i - 1][pos] - a[i][pos - 1] - a[i - 1][pos - 1]; if (a[i][pos] < 0 || a[i][pos] > 1) { ok = false; break; } a[pos][i] = sum[pos - 1][i - 1] - a[pos][i - 1] - a[pos - 1][i] - a[pos - 1][i - 1]; if (a[pos][i] < 0 || a[pos][i] > 1) { ok = false; break; } } if (ok) { go(pos + 1, sum, a); } } } } }
Comments