poj3279搜索详解

这道搜索题和大部分的题都不太一样，没有一个明显的思路，格子间的状态都是互相影响的，只能通过枚举第一行，逐行往下搜。

详解：

1、如何搜索：如果从上到下搜索，当前行是否需要反转取决于上一行的状态，通过翻转当前行使上一行为0，而不是通过上一行翻转为0后，看当前行的状态判断自己是否需要翻转，否则还会继续影响上一行。所以枚举一下第一行所有的状态，搜索到最后一行结束，如果可以保证最后一行都是0，那么方案可以，否则重新定义第一行的状态，继续搜索，找出使反转次数最少的方案。

2、保证字典序最小：按照字典序从小到大搜索（如何实现看下文）

Tips：

如何枚举：如果一行有N个格子，每个格子有两种状态，那么一共有2^n种，例如n = 6；001100则指第2、3位（i从0开始）翻转。字典序从小到大就是i从0到1<<n遍历（从一行的最后一位开始考虑翻转）

获取第一行定义的状态 i>>j &1：i>>j为 i 状态下第j位状态，为什么&1？因为题里定义0是不需要反转的，在get函数中判断某行某一位是否翻转也要注意一下，get函数中枚举上下左右及本身的5个格子，累加这几个格子的翻转值，假如这5个格子中有s个翻转过，那么此时这个格子就相当于原来的格子翻转了s次，加上原来的状态，和1相与便是这个格子的是否需要翻转的值。大家可以想一下如果初始问题设置为（0需要翻转，1不需要）时，就是和0相与了。

有点绕，当前行是否需要反转取决于上一行的是否为黑色！！

 1 #include <stdio.h>
 2 #include <iostream>
 3 #include <string>
 4 #include <algorithm>
 5 #include <string>
 6 #include <string.h>
 7 #include <math.h>
 8 #include <queue>
 9 #define MAXN 16
10 #define INF 1<<30
11 using namespace std;
12 
13 int a[MAXN][MAXN],flip[MAXN][MAXN],ans[MAXN][MAXN];
14 int m,n;
15 int dx[5] = {0,1,0,-1,0};
16 int dy[5] = {-1,0,0,0,1};
17 int get(int x,int y)
18 {
19     int cnt = a[x][y];//当前为t的格子，翻过n次后，状态与(t+n)%2等价
20     for(int i = 0;i<5;i++)
21     {
22         int a = x + dx[i];
23         int b = y + dy[i];
24         if(a>=0&&a<m&&b>=0&&b<n)
25             cnt += flip[a][b];
26     }
27     return cnt&1;
28 }
29 int cal()
30 {
31     int i,j;
32     for(i = 1;i<m;i++)
33     {
34         for(j = 0;j<n;j++)
35         {
36             if(get(i-1,j))
37                 flip[i][j] = 1;
38         }
39     }
40     for(i = 0;i<n;i++)
41     {
42         if(get(m-1,i))//（i-1，j)为黑色，则反转（i，j)
43             return INF;
44     }
45     int cnt = 0;
46      for(i = 0;i<m;i++)
47         for(j = 0;j<n;j++)
48             cnt+=flip[i][j];
49 
50     return cnt;
51 }
52 int main()
53 {
54     freopen("caicai.txt","r",stdin);
55     while(cin>>m>>n)
56     {
57         int i,j;
58         for(i = 0;i<m;i++)
59             for(j = 0;j<n;j++)
60             cin>>a[i][j];
61         int cnt = INF;
62         for(i = 0;i < 1<<n ;i++)
63         {
64             memset(flip,0,sizeof(flip));
65             for(j = 0;j<n;j++)
66             {
67                 flip[0][j] = i>>j & 1;
68             }
69             int temp = cal();
70             if(temp < cnt)
71             {
72                 cnt = temp;
73                 for(int p  = 0;p<m;p++)
74                     for(int q = 0;q<n;q++)
75                         ans[p][q] = flip[p][q];
76             }
77 
78         }
79         if(cnt == INF)
80             cout<<"IMPOSSIBLE
";
81         else{
82             for(i = 0;i<m;i++)
83             {
84                 for(j = 0;j<n;j++)
85                 {
86                     cout<<ans[i][j];
87                     if(j!=n-1)
88                         cout<<' ';
89                     else
90                         cout<<'
';
91                 }
92             }
93         }
94 
95     }
96     return 0;
97 }