Hướng dẫn giải của Trò chơi dò mìn
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; 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; }
Bình luận