Hướng dẫn giải của Aladdin
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
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); } } } } }
Bình luận