偶数矩阵-回溯

  1 #include <stdio.h>
  2 #include <mem.h>
  3 /*输入测试 
  4 0 0 0
  5 1 0 0
  6 0 0 0
  7 6
  8 0 0 0 0 0 0
  9 1 0 0 0 0 0
 10 0 0 0 0 0 0
 11 0 0 0 0 0 0 
 12 0 0 0 0 0 0
 13 0 0 0 0 0 0
 14 */
 15 
 16 int T,n;
 17 int map[256];//矩阵数组 
 18 int minuteTimes=9999;//初始化最大转换数9999，也就是无法形成偶数矩阵 
 19 int currentTimes=0;//当前转换数 
 20 int dirction[]={16,1,-1,-16};//偶数矩阵特性 
 21 //int recode[225]={0};//记录形成的偶数矩阵 
 22 
 23 //是否符合偶数矩阵特性 
 24 int isEven(int position)
 25 {
 26     int temp;
 27     int index=0;
 28     
 29     while(map[position+dirction[index++]]==2);
 30     
 31     temp=map[position+dirction[--index]];
 32     
 33     for(int i=index+1;i<4;i++)
 34     {
 35         if(map[position+dirction[i]]<2)    temp^=map[position+dirction[i]];
 36     }
 37     
 38     return    temp;
 39 }
 40 
 41 //寻找最小翻转次数 
 42 void findMinuteTimes(int depth)
 43 {
 44     if(depth>(n<<4)+n)    
 45     {
 46         if(currentTimes<minuteTimes)    
 47         {
 48             
 49             bool isOK=true;
 50             for(int i=0;i<256;i++)
 51             {
 52                 if(map[i]==2)    continue;
 53                 
 54                 if(isEven(i))
 55                 {
 56                     isOK=false;
 57                     break;
 58                 }
 59             }
 60             if(!isOK)    return;
 61             /*记录数组-调试使用 
 62             memset(recode,0,sizeof(recode));
 63             for(int i=0;i<256;i++)
 64             {
 65                 if(map[i]==1)    recode[(i/16-1)*15+i%16-1]=1;
 66             }
 67             */
 68             minuteTimes=currentTimes;
 69         }
 70         
 71         return;
 72     }
 73     if(map[depth]<2 && isEven(depth))
 74     {
 75         for(int i=0;i<4;i++)
 76         {
 77             if(map[depth+dirction[i]]>0)    continue;
 78             
 79             map[depth+dirction[i]]=1;
 80             currentTimes++;
 81             
 82             int temp;
 83             switch(i)
 84             {
 85                 //当选择步长为16时，应从+1，-1，-16中不超出数组的地方开始搜索 
 86                 case 0:
 87                      if(map[depth+dirction[i]+1]!=2)    temp=dirction[i]+1;
 88                 //当选择步长为1时，应从-1，-16中不超出数组的地方开始搜索      
 89                 case 1:
 90                      if(map[depth+dirction[i]-1]!=2)    temp=+dirction[i]-1;
 91                 //当选择步长为-1时，应从-16中不超出数组的地方开始搜索          
 92                 case 2:
 93                      if(map[depth+dirction[i]-16]!=2)    temp=dirction[i]-16;
 94                      break;
 95                 //否则递增1再开始搜索 
 96                 default:
 97                     temp=1;
 98             }
 99             findMinuteTimes(depth+temp);
100             map[depth+dirction[i]]=0;
101             currentTimes--;
102         }
103     }
104     else    findMinuteTimes(depth+1);
105             
106 }
107 
108 int main()
109 {
110     scanf("%d",&T); 
111     while(T--)
112     {
113         scanf("%d",&n);
114         minuteTimes=9999;
115         for(int i=0;i<16;i++)
116         {
117             for(int j=0;j<16;j++)
118             {
119                 if(i==0 || j==0)    map[(i<<4)+j]=2;
120                 else if(i<=n && j<=n)    scanf("%d",map+(i<<4)+j);
121                 else        map[(i<<4)+j]=2;
122             }    
123         }
124         findMinuteTimes(0);
125         printf("%d\n",minuteTimes==9999?-1:minuteTimes);
126     }
127     /*调试输出 
128     for(int i=0;i<n;i++)
129     {
130         for(int j=0;j<n;j++)
131         {
132             printf("%d ",recode[(i*15)+j]);
133         }
134         printf("\n");
135     }
136     for(int i=0;i<16;i++)
137     {
138         for(int j=0;j<16;j++)
139         {
140             printf("%d ",map[(i<<4)+j]);
141         }
142         printf("\n");
143     }
144     */
145     return 0;
146 }