题目：http://poj.org/problem?id=1753
题意就是给出一个棋盘，然后，每次翻转一个棋子，翻转的规则就是与该棋子相邻的棋子也要翻转，然后问是否能够达到一种棋盘上的棋子都是同一种颜色的状态。
思路：之前是想到每个棋子只有黑白两种颜色，然后就可以用一个十六位的二进制数来表示当前棋盘的状态，至于翻转就直接模拟一下，不知道为什么模拟的没成功，估计就算成功也效率也特别低，后来看到有人用位运算，而且特别简单，就借鉴学习一下。位运算真是个好东西^v^
代码：
#include<cstdio> #include<cstring> #include<queue> using namespace std; char str[5][5]; bool visited[66000]; struct Point{ int state; int step; }; //棋盘从左至右从上到下分别表示二进制的0 ~ 15位，翻转的时候第i位就用2^(i - 1)这个数来跟原来那个数进行异或就行 //因为每个棋子都还要跟它周围的棋子一起翻转，所以某个位置的翻转值除了该位子上棋子的翻转值还得加上周围棋子的翻转值 int flip[16] = {19, 39, 78, 140, 305, 626, 1252, 2248, 4880, 10016, 20032, 35968, 12544, 29184, 58368, 51200}; void BFS(Point s) { queue<Point>Q; Q.push(s); Point hd, t; while(!Q.empty()) { hd = Q.front(); Q.pop(); if(hd.state == 0|| hd.state == 0xffff) { printf("%d\n", hd.step); return; } for(int i = 0; i < 16; ++ i) { t.state = hd.state ^ flip[i]; if(visited[t.state]) { continue; } t.step = hd.step + 1; visited[t.state] = true; Q.push(t); } } printf("Impossible\n"); } int main() { freopen("poj1753.txt", "r", stdin); int s = 0; for(int i = 0; i < 4; ++ i) { for(int j = 0; j < 4; ++ j) { scanf("%c", &str[i][j]); s <<= 1; if(str[i][j] == 'b') { s += 1; } } getchar(); } memset(visited, false, sizeof(visited)); Point start; start.state = s; start.step = 0; visited[s] = true; BFS(start); return 0; } |