1805846_ac_0ms_48k.c

北大大牛代码 1240道题的原代码 超级权威

# include <stdio.h>
# include <stdlib.h>
 
int m,n,NO,tmp,mined,a[42][42],mark[42][42],u[42][42];
char mine[42][42];
 
void f(int i,int j)
{
 if(i == 0 || j == 0 || i == m + 1 || j == n + 1) return ;
   mark[i][j] = u[i][j] = 1; a[i][j] = 9;
   if(a[i][j+1]) mark[i][j+1] = 1; else if(!mark[i][j+1]) f(i,j+1);
 if(a[i][j-1]) mark[i][j-1] = 1; else if(!mark[i][j-1]) f(i,j-1);
 if(a[i+1][j]) mark[i+1][j] = 1; else if(!mark[i+1][j]) f(i+1,j);
 if(a[i+1][j+1]) mark[i+1][j+1] = 1; else if(!mark[i+1][j+1]) f(i+1,j+1);
 if(a[i+1][j-1]) mark[i+1][j-1] = 1; else if(!mark[i+1][j-1]) f(i+1,j-1);
 if(a[i-1][j+1]) mark[i-1][j+1] = 1; else if(!mark[i-1][j+1]) f(i-1,j+1);
 if(a[i-1][j]) mark[i-1][j] = 1; else if(!mark[i-1][j]) f(i-1,j);
 if(a[i-1][j-1]) mark[i-1][j-1] = 1; else if(!mark[i-1][j-1]) f(i-1,j-1);
 return ;
}
 void get_no()
{
   int i,j;
   for(i = 1; i < m + 1; i++)
    for(j = 1; j < n + 1; j++)
      if(mine[i][j] == 'M')
       {
        a[i][j]=-10;
        a[i][j+1]++;
        a[i][j-1]++;
        a[i+1][j+1]++;
        a[i+1][j]++;
        a[i+1][j-1]++;
        a[i-1][j+1]++;
        a[i-1][j]++;
        a[i-1][j-1]++;
       }           
}
 int scan_data()
{
    int i,j,li,lj,N,M,C,flag = 1,flag1;
     tmp = 10000;
    for(i = 1; i < m + 1; i++)
      for(j = 1; j < n + 1; j++)
      if(a[i][j] == 0)
      {   
         mined = flag = 0;
          for(li = 1; li < m + 1; li++)
          for(lj = 1; lj < n + 1; lj++)
          u[li][lj] = 0;
               f(i,j);
        k: for(li = 1; li < m + 1; li++)
              for(lj = 1; lj < n + 1; lj++)
              {   
                  N = M = 0;
                  if(a[li][lj]>0&&a[li][lj]<9&&mark[li][lj] == 1)
                  {  
                     if(!mark[li][lj+1])   M++;
                     if(!mark[li][lj-1])   M++;
                     if(!mark[li+1][lj+1]) M++;
                     if(!mark[li+1][lj])   M++;
                     if(!mark[li+1][lj-1]) M++;
                     if(!mark[li-1][lj+1]) M++;
                     if(!mark[li-1][lj])   M++;
                     if(!mark[li-1][lj-1]) M++;
                     if(mine[li][lj+1] == 'M')if(mark[li][lj+1])   N++;
                     if(mine[li][lj-1] == 'M')if(mark[li][lj-1])   N++;
                     if(mine[li-1][lj+1] == 'M')if(mark[li-1][lj+1]) N++;
                     if(mine[li-1][lj] == 'M')if(mark[li-1][lj])   N++;
                     if(mine[li-1][lj-1] == 'M')if(mark[li-1][lj-1]) N++;
                     if(mine[li+1][lj+1] == 'M')if(mark[li+1][lj+1]) N++;
                     if(mine[li+1][lj] == 'M')if(mark[li+1][lj])   N++;
                     if(mine[li+1][lj-1] == 'M')if(mark[li+1][lj-1]) N++;
                     C = a[li][lj];
                     if(C == N||C == M + N)
                     {  flag1  = 1;mark[li][lj] = 2;
                        if(!a[li][lj+1]||(!u[li][lj+1]&&a[li][lj+1]==9)) f(li,lj+1);
                        if(!a[li][lj-1]||(!u[li][lj-1]&&a[li][lj-1]==9)) f(li,lj-1);
                        if(!a[li+1][lj+1]||(!u[li+1][lj+1]&&a[li+1][lj+1]==9)) f(li+1,lj+1);
                        if(!a[li+1][lj]||(!u[li+1][lj]&&a[li+1][lj]==9)) f(li+1,lj);
                        if(!a[li+1][lj-1]||(!u[li+1][lj-1]&&a[li+1][lj-1]==9)) f(li+1,lj-1);
                        if(!a[li-1][lj+1]||(!u[li-1][lj+1]&&a[li-1][lj+1]==9)) f(li-1,lj+1);
                        if(!a[li-1][lj]||(!u[li-1][lj]&&a[li-1][lj]==9)) f(li-1,lj);
                        if(!a[li-1][lj-1]||(!u[li-1][lj-1]&&a[li-1][lj-1]==9)) f(li-1,lj-1);
                        if(!mark[li][lj+1])   mark[li][lj+1] = 1;
                        if(!mark[li][lj-1])   mark[li][lj-1] = 1;
                        if(!mark[li+1][lj+1]) mark[li+1][lj+1] = 1;
                        if(!mark[li+1][lj])   mark[li+1][lj] = 1;
                        if(!mark[li+1][lj-1]) mark[li+1][lj-1] = 1;
                        if(!mark[li-1][lj+1]) mark[li-1][lj+1] = 1;
                        if(!mark[li-1][lj])   mark[li-1][lj] = 1;
                        if(!mark[li-1][lj-1]) mark[li-1][lj-1] = 1;
                     }
                  }
              }
              if(flag1) {flag1 = 0;goto k;}
              for(li = 1; li < m + 1; li++)
                  for(lj = 1; lj < n + 1; lj++)
              if(a[li][lj] >= 0 && mark[li][lj] == 0)
              mined++;
              if(mined < tmp) tmp = mined;
          for(li = 1; li < m + 1; li++)
              for(lj = 1; lj < n + 1; lj++)
              mark[li][lj] = 0;
      } 
      if(flag) return m * n - NO -1;
      else return tmp;
}
 
int main()
{
  int i,j;
  while(1)
 {
   NO = 0; 
   scanf("%d %d",&m,&n);
   if(m == 0 && n == 0)
   break;
   getchar();
   for(i = 0; i <= n + 1; i++)
   { mine[0][i] = mine[m+1][i] = '.'; mark[0][i] = mark[m+1][i] = 1; }
   for(i = 1; i < m + 1; i++)
    {
      mine[i][0] = mine[i][n+1] = '.';
      mark[i][0] = mark[i][n+1] = 1;
      scanf("%s",&mine[i][1]);
    }
    get_no(); 
    for(i = 1; i < m + 1; i++)
     for(j = 1; j < n + 1; j++)
      if(mine[i][j] == 'M') NO++;
      printf("%d\n",scan_data());
    for(i = 0;i < 42; i++)
      for(j = 0;j < 42; j++)
         a[i][j] = mark[i][j] = 0;
    }
 return 0;
}