POJ-1753 传 送
题目翻译：
翻转游戏是在一个矩形的4x4场上进行的，在其16个正方形的每个正方形上放置了两个棋子。每块的一侧为白色，另一侧为黑色，并且每一块都以黑色或白色的一面朝上。每轮翻转3到5片，从而将其上侧的颜色从黑色更改为白色，反之亦然。根据以下规则，每轮选择要翻转的棋子： 选择16件中的任何一件。 将选定的片段以及所有相邻片段翻转到选定片段的左侧，右侧，顶部和底部（如果有）。
考虑以下位置作为示例：
bwbw
wwww
bbwb
bwwb
在此，“ b”表示其黑色面朝上的片，“ w”表示其白色面朝上的片。如果我们选择从第三行翻转第一块（此选择如图所示），那么该字段将变为：
bwbw
bwww
wwwb
wwwb
游戏的目标是将所有白色的一面朝上或将所有黑色的一面朝上翻转。您将编写一个程序，该程序将搜索实现此目标所需的最少回合数。
输入项
输入包括4行，每行分别包含4个字符“ w”或“ b”，表示游戏场的位置。
输出量
向输出文件中写入一个整数-从给定位置达到游戏目标所需的最少回合数。如果最初达到了目标，则写0。如果不可能达到目标，则写“Impossible”（不带引号）。
样本输入
bwwb
bbwb
bwwb
bwww
样本输出
4
思路：
单纯的暴力深搜，因为棋盘不大（最主要的原因是目前只会用这个方法 ）。每个棋子都有两种情况，翻或者不翻，翻的话就要把 本身和上下左右四个棋子 同时翻，然后回溯时翻回来，不断比较棋盘清一色时，得到最少的操作次数。
代码：
#include <iostream>
#include <algorithm>
using namespace std
;
char chess
[4][4],now
[]={'w','b'};
int ans
=1<<27;
char revise(char c
)
{
if(c
==now
[0]) return now
[1];
else return now
[0];
}
bool in(int x
,int y
)
{
if(x
>=0 && x
<4 && y
>=0 && y
<4)
return 1;
return 0;
}
bool isOk(char chess
[4][4])
{
for(int i
=0;i
<4;i
++)
for(int j
=0;j
<4;j
++)
if(chess
[i
][j
]!=chess
[0][0]) return 0;
return 1;
}
void op(int x
,int y
)
{
chess
[x
][y
]=revise(chess
[x
][y
]);
if(in(x
+1,y
)) chess
[x
+1][y
]=revise(chess
[x
+1][y
]);
if(in(x
-1,y
)) chess
[x
-1][y
]=revise(chess
[x
-1][y
]);
if(in(x
,y
-1)) chess
[x
][y
-1]=revise(chess
[x
][y
-1]);
if(in(x
,y
+1)) chess
[x
][y
+1]=revise(chess
[x
][y
+1]);
}
void dfs(int x
,int y
,int k
)
{
if(isOk(chess
))
{
ans
=min(ans
,k
);
return;
}
if(!in(x
,y
)) return;
int newy
=(y
+1)%4;
int newx
=x
+(y
+1)/4;
dfs(newx
,newy
,k
);
op(x
,y
);
dfs(newx
,newy
,k
+1);
op(x
,y
);
}
int main()
{
for(int i
=0;i
<4;i
++)
for(int j
=0;j
<4;j
++)
cin
>>chess
[i
][j
];
dfs(0,0,0);
if(ans
==1<<27) cout
<<"Impossible";
else cout
<<ans
;
return 0;
}
