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.

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

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.