题目链接

POJ 1753

题目大意

4*4的棋盘，放置了16个白色和黑色的两种棋子，进行翻转操作（上下左右中都变反），计算全部为一个颜色最小的次数

题目思路

▶ 只有两种状态→看成0和1→4*4的棋盘看成16位的二进制数 ① 每一种状态对应一个数字，只要看这个数字有没有重复出现，就知道了这个状态出现了几次 ② 16个位置依次翻转判断就xin啦

代码

#include<iostream> #include<cstring> #include<cstdlib> #include<string> #include<queue> #include<cmath> #include<vector> #include<bitset> #include<cstdio> using namespace std; int pos[5]= {0,-1,1,-4,4}; //上下左右中 bool record[99999]; //包含2的16次方 int main() { bitset<16> b; char ch; int c = 0; for(int i=0; i<16; i++) //只用判断一个，另一个自动粗来 { cin>>ch; if(ch == 'b') { b[i] = 1; c++; } else b[i]=0; } if(c==16 || c==0) //一开始直接 { cout<<"0"<<endl; return 0; } queue<bitset<16>> q; q.push(b); int cnt = 0; int f = -1; while(q.size()) { int len = q.size(); for(int k=0; k<len; k++) { bitset<16> temp = q.front(); q.pop(); int num=0; for(int i=0; i<16; i++) if(temp[i]) num++; if(num==0 || num==16) { f = cnt; break; } if(f!=-1) break; int re = temp.to_ulong(); if(record[re]) continue; record[re] = 1; for(int i=0; i<16; i++) { bitset<16> bb(temp); int x = i/4; //第几行 int y = i%4; //第几列 for(int j=0; j<5; j++) { if(y==0 && j==1) continue; if(y==3 && j==2) continue; if(x==0 && j==3) continue; if(x==3 && j==4) continue; bb.flip(x*4+y+pos[j]); } q.push(bb); } } if(f!=-1) break; cnt++; } if(f!=-1) cout<<f<<endl; else cout<<"Impossible"<<endl; return 0; }

总结

① 两个状态，看成01，进行位运算，用自带的函数，如flip，tolong，方便快捷~ ② 把棋盘看成一列之后，第几行第几列的表达方式