NKMINES - Trò chơi dò mìn

Tác giả: hieult

Ngôn ngữ: C++

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

Download