Editorial for Trò chơi dò mìn
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; dx:array[1..8] of longint=(-1,-1,-1,0,0,1,1,1); dy:array[1..8] of longint=(-1,0,1,-1,1,-1,0,1); type ar=array[1..maxn,1..maxn] of longint; var n,m,dem:longint; a,b:ar; qx,qy:array[0..maxn*maxn] of longint; procedure rf; var i,j:longint; begin read(m,n); for i:=1 to m do for j:=1 to n do read(b[i,j]); qx[1]:=1; qy[1]:=1; dem:=1; for i:=3 to m+n do for j:=max(1,i-n) to min(m,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 m do begin for j:=1 to n do write(a[i,j],' '); writeln; end; halt; end; procedure edit(x,y,val:longint); var xx,yy,i:longint; begin for i:=1 to 8 do begin xx:=x+dx[i]; yy:=y+dy[i]; if (xx>0) and (xx<=m) and (yy>0) and (yy<=n) then b[xx,yy]:=b[xx,yy]+val; end; end; function ok:boolean; var i:longint; begin for i:=1 to n do if b[m,i]<>0 then exit(false); for i:=1 to m do if b[i,n]<>0 then exit(false); exit(true); end; procedure att(p:longint); var i,j,x,y,xx,yy:longint; c0,c1:boolean; begin if p>dem then begin if ok then wf else exit; end; 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); end; begin assign(input,fi); reset(input); rf; pr; close(input); end.
Code mẫu của ladpro98
program nkmines; uses math; const fi=''; maxn=222; dx:array[1..8] of longint = (-1,-1,-1,0,0,1,1,1); dy:array[1..8] of longint = (-1,0,1,-1,1,-1,0,1); var a,p:array[1..maxn,1..maxn] of longint; m,n:longint; procedure input; var inp:text; i,j:longint; begin assign(inp,fi);reset(inp); readln(inp,m,n); for i:=1 to m do begin for j:=1 to n do read(inp,a[i,j]); readln(inp); end; close(inp); end; function test(i,j,q:longint):boolean; var x,y,k,t:longint; begin t:=0; for k:=1 to 8 do begin x:=i+dx[k];y:=j+dy[k]; if (1<=x) and (x<=m) and (1<=y) and (y<=n) and (p[x,y]=1) then inc(t); end; if t>a[i,j] then exit(false); if q=1 then if t=a[i,j] then exit(true) else exit(false); if q=2 then if (t>=a[i,j]-1) then exit(true) else exit(false); if q=3 then if (t>=a[i,j]-3) then exit(true) else exit(false); if q=4 then if (t>=a[i,j]-2) then exit(true) else exit(false); if q=5 then if (t>=a[i,j]-5) then exit(true) else exit(false); if q=6 then if (t>=a[i,j]-4) then exit(true) else exit(false); if q=7 then if (t>=a[i,j]-6) then exit(true) else exit(false); if q=8 then if (t>=a[i,j]-7) then exit(true) else exit(false); end; procedure output; var i,j:longint; begin for i:=1 to m do begin for j:=1 to n do write(p[i,j],' '); writeln; end; end; procedure back(i,j,sx,sy:longint); var k,x,y,v:longint; t:boolean; begin if i>m then begin output; halt; end; for v:=0 to 1 do begin p[i,j]:=v; t:=true; for k:=1 to 8 do begin x:=i+dx[k]; y:=j+dy[k]; if (1<=x) and (x<=m) and (1<=y) and (y<=n) then t:=test(x,y,k); if not t then break; end; if t then begin x:=i+1;y:=j-1; if (1<=x) and (x<=m) and (1<=y) and (y<=n) then back(x,y,sx,sy) else begin if (sx=1) then if sy<n then back(sx,sy+1,sx,sy+1) else back(sx+1,sy,sx+1,sy) else back(sx+1,sy,sx+1,sy); end; end; end; p[i,j]:=0; end; begin input; back(1,1,1,1); end.
Code mẫu của RR
{$R+,Q+} PROGRAM NKMINES; CONST FINP=''; FOUT=''; maxn=401; VAR c,a:array[0..maxn+1,0..maxn+1] of integer; m,n,kt:integer; procedure readInput; var f:text; i,j:integer; begin assign(f,FINP); reset(f); readln(f,m,n); for i:=1 to m do for j:=1 to n do read(f,c[i,j]); for i:=0 to n+1 do begin c[0,i]:=100; c[m+1,i]:=100; end; for j:=0 to m+1 do begin c[j,0]:=100; c[j,n+1]:=100; end; if m<n then kt:=n else kt:=m; close(f); end; procedure writeOutput; var f:text; i,j:integer; begin assign(f,FOUT); rewrite(f); for i:=1 to m do begin for j:=1 to n do write(f,a[i,j],' '); writeln(f); end; close(f); halt; end; function dienSo(k:integer):boolean; var i,j:integer; ok:boolean; begin ok:=true; for i:=2 to k-2 do if c[i-1,k-i-1]>0 then if (i<=m) and (k-i-1<=n) then begin j:=k-i; if c[i-1,j-1]>1 then ok:=false; a[i,j]:=1; dec(c[i-1,j-1]); if c[i-1,j-1]<0 then ok:=false; dec(c[i-1,j]); if c[i-1,j]<0 then ok:=false; dec(c[i-1,j+1]); if c[i-1,j+1]<0 then ok:=false; dec(c[i,j-1]); if c[i,j-1]<0 then ok:=false; dec(c[i,j+1]); if c[i,j+1]<0 then ok:=false; dec(c[i+1,j-1]); if c[i+1,j-1]<0 then ok:=false; dec(c[i+1,j]); if c[i+1,j]<0 then ok:=false; dec(c[i+1,j+1]); if c[i+1,j+1]<0 then ok:=false; end; dienSo:=ok; end; procedure xoaSo(k:integer); var i,j:integer; begin for i:=2 to k-2 do if a[i,k-i]=1 then begin j:=k-i; a[i,j]:=0; inc(c[i-1,j-1]); inc(c[i-1,j]); inc(c[i-1,j+1]); inc(c[i,j-1]); inc(c[i,j+1]); inc(c[i+1,j-1]); inc(c[i+1,j]); inc(c[i+1,j+1]); end; end; function kiemtra:boolean; var i,j:integer; begin kiemtra:=false; for i:=1 to m do for j:=1 to n do if c[i,j]<>0 then exit; kiemtra:=true; end; procedure try(i:integer); var j1,j2:byte; ok:boolean; begin for j2:=0 to 1 do for j1:=0 to 1 do if (i<=n) or (j1=0) then if (i<=m) or (j2=0) then begin ok:=true; a[1,i]:=j1; if j1=1 then begin dec(c[1,i-1]); if c[1,i-1]<0 then ok:=false; dec(c[1,i+1]); if c[1,i+1]<0 then ok:=false; dec(c[2,i-1]); if c[2,i-1]<0 then ok:=false; dec(c[2,i]); if c[2,i]<0 then ok:=false; dec(c[2,i+1]); if c[2,i+1]<0 then ok:=false; end; a[i,1]:=j2; if j2=1 then begin dec(c[i-1,1]); if c[i-1,1]<0 then ok:=false; dec(c[i+1,1]); if c[i+1,1]<0 then ok:=false; dec(c[i-1,2]); if c[i-1,2]<0 then ok:=false; dec(c[i+1,2]); if c[i+1,2]<0 then ok:=false; dec(c[i,2]); if c[i,2]<0 then ok:=false; end; if ok then ok:=dienSo(i+1); if ok then begin if i<kt+kt-1 then try(i+1) else if kiemtra then writeOutput; end; if j1=1 then begin inc(c[1,i-1]); inc(c[1,i+1]); inc(c[2,i-1]); inc(c[2,i]); inc(c[2,i+1]); end; if j2=1 then begin inc(c[i-1,1]); inc(c[i+1,1]); inc(c[i-1,2]); inc(c[i+1,2]); inc(c[i,2]); end; xoaSo(i+1); end; end; procedure solve; begin a[1,1]:=0; try(2); fillchar(a,sizeof(a),0); a[1,1]:=1; dec(c[1,2]); dec(c[2,1]); dec(c[2,2]); if c[1,2]<0 then exit; if c[2,1]<0 then exit; if c[2,2]<0 then exit; try(2); end; BEGIN readInput; solve; END.
Code mẫu của hieult
#include<algorithm> using namespace std; #define FORE(i, a, b) for(int i=(a), _b=(b); i<=_b; i++) const int DBG = 0; const int HOME = 0; int m, n; int a[202][202], c[202][202]; int nextr[202][202], nextc[202][202]; inline int sum(int u, int v){ return a[u-1][v-1]+a[u-1][v]+a[u-1][v+1]+ a[u ][v-1]+ +a[u ][v+1]+ a[u+1][v-1]+a[u+1][v]+a[u+1][v+1]; } bool Try(int u, int v){ int t, u2,v2; if(u==m || v==1){ if(u+v>=n) { v2 = n; u2 = u+v+1-v2;} else { u2 = 1; v2= u+v+1-u2;} } else{ u2 = u+1; v2 = v-1;} if(u==m && v==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(u2, v2)) return true; a[u][v]=1; if(Try(u2, v2)) return true; return false; } if(v==1){ a[u][v]=0; if(Try(u2, v2)) return true; a[u][v]=1; if(Try(u2, v2)) 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==m && 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(u2, v2)) return true; return false; } int main(){ if(HOME){ freopen("mines.inp", "r", stdin); freopen("mines.out", "w", stdout); } scanf("%d %d", &m, &n); FORE(i, 1, m) FORE(j, 1, n) scanf("%d", &c[i][j]); memset(a, 0, sizeof a); FORE(i, 0, 1){ a[1][1]=i; if(Try(1,2)) break; } FORE(i, 1, m) FORE(j, 1, n) printf("%d%c", a[i][j], j==n?'\n':' '); return 0; }
Code mẫu của khuc_tuan
#include <iostream> using namespace std; int m, n; int a[222][222]; int b[222][222], bluu[222][222]; bool daxong; bool inside( int i,int j) { return (i>=0) && (i<m) && (j>=0) && (j<n); } int check(int i,int j) { int total = a[i][j]; for(int di=-1;di<=1;++di) for(int dj=-1;dj<=1;++dj) if(di!=0 || dj!=0) { int x = i + di; int y = j + dj; if(inside( x, y)) total -= b[x][y]; } return total; } bool process(int i) { for(int j=1;j<i;++j) if(inside(i,j)) { b[i][j] = 0; int t = check( i-1, j-1); if(t!=0 && t!=1) return false; b[i][j] = t; } for(int j=1;j<i;++j) if(inside(j,i)) { b[j][i] = 0; int t = check( j-1, i-1); if(t!=0 && t!=1) return false; b[j][i] = t; } if(inside(i,i)) { b[i][i] = 0; int t = check(i-1,i-1); if(t!=0 && t!=1) return false; b[i][i] = t; } return true; } //int dem = 0; void duyet(int i) { if(daxong) return; if(i>=m && i>=n) { //++dem; bool ok = true; for(int j=0;j<m;++j) if(check(j,n-1)!=0) { //if(dem==2) cout << j << " " << n-1 << " " << check(j,n-1) << " " << a[j][n-1] << endl; ok = false; break; } for(int j=0;j<n;++j) if(check(m-1,j)!=0) { //if(dem==2) cout << m-1 << " " << j << " " << check(m-1,j) << " " << a[m-1][j] << endl; ok = false; break; } if(!ok) return; daxong = true; //for(int i=0;i<m;++i) { for(int j=0;j<n;++j) printf("%d ", b[i][j]); puts(""); } //puts(""); //cout << check(0, 3) << " " << a[0][3] << endl << endl; memmove( bluu, b, sizeof(b)); return; } if(i==0) { b[0][0] = 0; duyet(i+1); b[0][0] = 1; duyet(i+1); return; } for(b[i][0]=0;b[i][0]<2;++b[i][0]) for(b[0][i]=0;b[0][i]<2;++b[0][i]) { bool ok = process(i); if(ok) duyet(i+1); } } int main() { scanf("%d%d", &m, &n); for(int i=0;i<m;++i) for(int j=0;j<n;++j) scanf("%d", &a[i][j]); daxong = false; duyet(0); for(int i=0;i<m;++i) { for(int j=0;j<n;++j) printf("%d ", bluu[i][j]); printf("\n"); } //system("pause"); return 0; }
Comments