题意 ： 给你一个矩阵，有黑有白，翻转一个块可以让上下左右都翻转过来，问最少翻转多少次能让矩阵变为全白。
思路 ： 我们从第一行开始枚举要翻转的状态，最多可以枚举到2的16次方，因为你只要第一行的确定了，第二行要翻转的也就确定了，所以第一行的状态决定了最后的状态。看了网上大神，真是让位运算废了啊，，，，，太复杂了。。。。。。
1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 #include <map> 5 6 using namespace std; 7 8 const int INF = 999999999 ; 9 int r,c,n; 10 int data[17] ; 11 12 void Init() 13 { 14 char mapp[17][17] ; 15 memset(data,0,sizeof(data)) ; 16 if(r >= c) 17 { 18 for(int i = 0 ; i < r ; i++)//每一行都用一个二进制数来保存 19 { 20 data[i] = 0 ; 21 scanf("%s",mapp[i]) ; 22 for(int j = 0 ; j < c ; j++) 23 { 24 if(mapp[i][j] == 'X') 25 data[i] |= 1 << j ;//这一行中将是X的地方全部存为1 26 } 27 } 28 } 29 else//优化，当列比较少的时候就翻转过来用列。 30 { 31 for(int i = 0 ; i < r ; i++) 32 { 33 data[i] = 0 ; 34 scanf("%s",mapp[i]) ; 35 for(int j = 0 ; j < c ; j++) 36 if(mapp[i][j] == 'X') 37 data[j] |= 1 << i ; 38 } 39 //把r和c的两值互换 40 r = r^c ; 41 c = r^c ; 42 r = r^c ; 43 } 44 } 45 void solve() 46 { 47 int minn = INF ; 48 int a[17],tmp[17] ; 49 for(int i = 0 ; i < (1 << c) ; i++)//枚举状态，共有2的c次方个 50 { 51 for(int j = 0 ; j < r ; j++) 52 a[j] = data[j] ; 53 for(int j = 0 ; j < r ; j++) 54 { 55 tmp[j] = j == 0 ? i : a[j-1] ; 56 a[j] ^= tmp[j] ;//本行要翻转 57 a[j] ^= tmp[j] >> 1 ;//右边也要翻转 58 a[j] ^= tmp[j] << 1 & ((1 << c)-1) ;//防止最左边的那位超出范围 59 a[j+1] ^= tmp[j] ;//下一行也要翻转 60 } 61 if(!a[r-1])//因为第一行确定之后第二行也就确定了，以此类推，只要判断最后一行是不是全白就行了 62 { 63 int cnt = 0 ; 64 for(int j = 0 ; j < r ; j++) 65 { 66 for(int k = tmp[j] ; k > 0 ; k >>= 1) 67 if(1 & k) cnt ++ ; 68 } 69 if(cnt < minn) minn = cnt ; 70 } 71 } 72 if(minn == INF) 73 printf("Damaged billboard. ") ; 74 else printf("You have to tap %d tiles. ",minn) ; 75 } 76 int main() 77 { 78 while(~scanf("%d %d",&r,&c)) 79 { 80 if(r == 0 && c == 0) 81 break ; 82 Init() ; 83 solve() ; 84 } 85 return 0; 86 }
如果那四行看不懂，没关系，因为我也看不太懂，看这里应该比较好理解一点，就是翻本行，翻左边那一列，右边那一列，下一行