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

Please read the guidelines before commenting.


There are no comments at the moment.