POJ 1753-Flip Game
1.原题
Description
Flip game is played on a rectangular 4x4 field with two-sided pieces placed on each of its 16 squares. One side of each piece is white and the other one is black and each piece is lying either it’s black or white side up. Each round you flip 3 to 5 pieces, thus changing the color of their upper side from black to white and vice versa. The pieces to be flipped are chosen every round according to the following rules:
1.Choose any one of the 16 pieces.
2.Flip the chosen piece and also all adjacent pieces to the left, to the right, to the top, and to the bottom of the chosen piece (if there are any).
Consider the following position as an example:
bwbw
wwww
bbwb
bwwb
Here “b” denotes pieces lying their black side up and “w” denotes pieces lying their white side up. If we choose to flip the 1st piece from the 3rd row (this choice is shown at the picture), then the field will become:
bwbw
bwww
wwwb
wwwb
The goal of the game is to flip either all pieces white side up or all pieces black side up. You are to write a program that will search for the minimum number of rounds needed to achieve this goal.
Input
The input consists of 4 lines with 4 characters “w” or “b” each that denote game field position.
Output
Write to the output file a single integer number – the minimum number of rounds needed to achieve the goal of the game from the given position. If the goal is initially achieved, then write 0. If it’s impossible to achieve the goal, then write the word “Impossible” (without quotes).
Sample Input
bwwb
bbwb
bwwb
bwww
Sample Output
4
Flip Game Image
2.题意
就是说选择4×4表格中的任意一个位置，然后这个位置和它的上下左右的位置都会转换颜色，然后就是问你怎样才能让整个4×4方格全是一种颜色，求一个最小的步数，不存在的话输出“Impossible”
3.我的思路
暴力求解，对步数进行限制，然后判定1步能否实现，然后判断2步能否实现，一直到判断出结果，但是这样的话其实只实现了0-5步是比较快的，但是6步以后就会运行时间增加很多，所以我的思路还是不正确的，但是还是贴下我的代码吧
4.我的代码（只能实现5步以内比较快）
#include
using namespace std;
typedef char State[4][4];
State state;
bool check(){
char start = state[0][0];
for (int i = 0;i<4;i++)
for (int j = 0;j<4;j++){
if(state[i][j] != start) return false;
}
return true;
}
char change(char p){
if(p == 'b') return 'w';
return 'b';
}
void changeColor(int i,int j){
if(i - 1 >= 0) state[i-1][j] = change(state[i-1][j]);
if(i + 1 < 4) state[i+1][j] = change(state[i+1][j]);
if(j + 1 < 4) state[i][j+1] = change(state[i][j+1]);
if(j - 1 >=0 ) state[i][j-1] = change(state[i][j-1]);
state[i][j] = change(state[i][j]);
}
bool searchP(int step){
if(step == 0) return false;
for (int i = 0;i<4;i++) {
for (int j = 0;j<4;j++) {
changeColor(i,j);
//printP();
if(check()) return true;
if(searchP(step-1)) return true;
else
changeColor(i,j);
}
}
return false;
}
int main(){
while(true) {
for (int i = 0;i<4;i++)
for (int j = 0;j<4;j++) cin>>state[i][j];
if(check()) {
cout<<"0"<<endl;
continue;
}
int i = 0;
while(++i){
if(searchP(i)) break;
}
cout<<i<<endl;
}
return 0;
}
5.思路（正解？）
我的方法之所以到后来速度很慢，是因为重复计算太多次了，正解应该是用一个VECTOR来保存状态，然后声明一个结构体，包含状态（即数组的状况）和已经走的步数，然后对这个栈进行维护，对栈中每一个元素进行广度遍历，再PUSH到VECTOR中，在建立一个vis的表，对已经运行过的VECTOR中的元素，不将其push进VECTOR中去，这样的话，如果存在的话，到时可以根据结构体中的步数来输出，如果到时VECTOR为空的话，就可以跳出，然后输出“Impossible”。
好的吧，只能说下面的代码可以保证我的输出肯定正确，但是运行时间呢，更慢了，要输出个Impossible的话，估计得刷个人人的时间了，很难忍受的，输出4以上的就会很慢了，主要是每次都要对string进行大量操作。弄得我都没有勇气提交POJ了
6.代码（正确？）
#include<iostream>
#include<queue>
#include<cstring>
#include<string>
#include<string.h>
using namespace std;
struct State
{
string board;
int step;
};
queue vS;
string visList[1000000];
int pp = 0;
bool check(State s){
string str = s.board;
const char* ch = str.c_str();
char start = ch[0];
for (int i = 0;i<4;i++) {
for (int j=0;j<4;j++) {
if(start != ch[i*4+j]) return false;
}
}
return true;
}
char change(char s){
if(s == 'b') return 'w';
return 'b';
}
bool isVis(string s){
for (int i = 0;i= 0) ch[x*4+y-1] = change(s[x*4+y-1]);
if(y + 1 < 4) ch[x*4+y+1] = change(s[x*4+y+1]);
if(x + 1 < 4) ch[(x+1)*4+y] = change(s[(x+1)*4+y]);
if(x - 1 >= 0) ch[(x-1)*4+y] = change(s[(x-1)*4+y]);
ch[x*4+y] = change(s[x*4+y]);
string sss;
sss.insert(0,ch);
return sss;
}
void getResult(){
State ss;
bool op = false;
while(!vS.empty()){
ss = vS.front();
if(check(ss)){
op = true;
break;
}
vS.pop();
for (int i=0;i<4;i++) {
for (int j=0;j<4;j++) {
string s = changeColor(ss.board,i,j);
if(isVis(s)) continue;
int step = ss.step + 1;
State ps;
ps.board = s;
ps.step = step;
vS.push(ps);
visList[pp++] = s;
}
}
}
if(op) cout<<ss.step<<endl;
else cout<<"Impossible"<<endl;
}
int main(){
while(true){
State startS;
while(!vS.empty()) vS.pop();
string input;
pp = 0;
memset(visList,0,sizeof(0));
for (int i = 0;i<4;i++) {
cin>>input;
startS.board.append(input);
}
visList[pp++] = input;
startS.step = 0;
vS.push(startS);
getResult();
}
return 0;
}
7.思路（正解）
这回肯定是正确的思路了，之前的思路其实也没错，重要是这里还要用一种叫“位运算”的方式来保存状态，这样可以更快的判断是否访问过，修改状态，很多都很方便，而且速度快。
8.代码（正解AC代码）
#include<iostream>
#include<queue>
#define M 65535
#define N 0
using namespace std;
struct state
{
int data;
int step;
};
char map[4][4];
int vis[65536];
queue sQ;
int bfs(int data) {
int i = 0;
state l;
state p;
l.data = data;
l.step = 0;
sQ.push(l);
vis[data] = 1;
while(!sQ.empty()) {
p = sQ.front();
sQ.pop();
if(p.data == M || p.data == N) return p.step;
else{
for (int i=0;i<16;i++) {
int elem = p.data;
elem = elem ^ (1 << i);
if(i > 3)
elem = elem^(1 << (i - 4));
if(i < 12)
elem = elem^(1 << (i + 4));
if(i % 4 != 0)
elem = elem^(1 << (i - 1));
if(i % 4 != 3)
elem = elem^(1 << (i + 1));
state q;
q.data = elem;
q.step = p.step + 1;
if(!vis[elem]){
vis[elem] = 1;
sQ.push(q);
}
}
}
}
while(!sQ.empty())
sQ.pop();
return -1;
}
int main(){
int i=0;
int j=0;
int data=0;
int step=0;
for (int i = 0;i < 4;i++) {
gets(map[i]);
for (int j=0;j<4;j++) {
if(map[i][j] == 'b')
data = (data << 1) + 1;
else
data = data << 1;
}
}
memset(vis,0,sizeof(vis));
step = bfs(data);
if(step == -1) cout<<"Impossible"<<endl;
else cout<<step<<endl;
return 0;
}