http://acm.pku.edu.cn/JudgeOnline/problem?id=1753
就是普通的广搜，状态存储用一位表示一个格是黑还是白（0黑1白），听大牛说可以通过异或运算来进行状态转移，不过我不会，就直接进行加减运算了。
#include<iostream> #include<stdlib.h> using namespace std; char board[4][4]; int hash[65536],state,temp_state,temp_i,temp_j; int dx[4] = {0,0,1,-1},dy[4] = {1,-1,0,0},queue_start,queue_end,result = 0,result_sum; int queue[100000],queue_sum[100000]; int main() { int i,j,k,sum; queue_start = 0; queue_end = 0; memset(hash,0,sizeof(hash)); memset(queue_sum,0,sizeof(queue_sum)); state = 0; for (i = 0;i < 4;i++) for (j = 0;j < 4;j++) { cin>>board[i][j]; if (board[i][j] == 'b') { state += 1<<(i*4+j); } } queue[queue_end++] = state; hash[state] = 1; while(queue_start < queue_end && !result) { state = queue[queue_start++]; temp_state = state; sum = 0; for (i = 0;i < 16;i++) { if (state&(1<<i)) sum++; } if (sum == 0 || sum == 16) { result = 1; result_sum = queue_sum[queue_start-1]; } for (i = 0;i < 4;i++) for (j = 0;j < 4;j++) { temp_state = state; temp_i = i; temp_j = j; if (state&(1<<(i*4+j))) temp_state -= 1<<(i*4+j); else temp_state += 1<<(i*4+j); for (k = 0;k <4;k++) { temp_i = i + dx[k]; temp_j = j + dy[k]; if (temp_i >=0 && temp_i < 4 && temp_j >=0 && temp_j < 4) { if (temp_state&(1<<(temp_i*4+temp_j))) { temp_state -= 1<<(temp_i * 4 + temp_j); } else { temp_state += 1<<(temp_i * 4 + temp_j); } } } if (!hash[temp_state]) { hash[temp_state] = 1; queue[queue_end] = temp_state; queue_sum[queue_end] = queue_sum[queue_start-1] + 1; queue_end++; } } } if (result) cout<<result_sum<<endl; else cout<<"Impossible"<<endl; system("Pause"); return 0; }
转载于:https://www.cnblogs.com/xinguohenan/archive/2009/05/09/1453294.html
相关资源：各显卡算力对照表！