作法: 與97高市資訊學科能力競賽 6. 按鈕問題 相同

DFS 窮舉

自行點閱

/************************************************************/

#include<stdio.h>
#include<stdlib.h>
int N=10,M=10,a,b,MIN;
char map[11][11];
void click(int x,int y)
{
   map[x][y]=1-map[x][y];
   if(x-1>=0)  map[x-1][y]=1-map[x-1][y];
   if(x+1<N)   map[x+1][y]=1-map[x+1][y];
   if(y-1>=0)  map[x][y-1]=1-map[x][y-1];
   if(y+1<M)   map[x][y+1]=1-map[x][y+1];
}
void DFS(int x,int y,int time)
{
   if(y==M) ++x,y=0;
  
   if(x==0)
      {
         DFS(x,y+1,time);
         click(x,y);/*按下*/
         DFS(x,y+1,time+1);
         click(x,y);/*還原*/
      }
   else if(x<N)
      {
          if(map[x-1][y]==0)  /*上面那格是開的*/
            {
               click(x,y);   /*則按下此格*/
               DFS(x,y+1,time+1);
               click(x,y);
            }
          else  DFS(x,y+1,time);
      }
   else
      {
         int a;
         for(a=0;a<M;a++)
            if(map[N-1][a]==0)
              return;
         if(time<MIN) MIN=time;
      }
}
main()
{
 int t;
 while(scanf("%d",&t)==1)
      while(t--)
      {
         for(a=0;a<10;a++)
            {
             scanf("%s",map[a]);
               for(b=0;b<10;b++)
                 map[a][b]=(map[a][b]=='O')?0:1; /*1開 2 關*/
            }
         MIN=2147483647;
         DFS(0,0,0);
         printf("%d\n",MIN);
      }
 return 0;
}