## 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.

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
for i:=1 to m do
for j:=1 to n do
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.


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);
for i:=1 to m do
begin
for j:=1 to n do read(inp,a[i,j]);
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;
var
f:text;
i,j:integer;
begin
assign(f,FINP); reset(f);
for i:=1 to m do
for j:=1 to n do
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
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];
}
}

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;
}