题面
在一个 4 * 4 的棋盘上，每个格子都摆着一个棋子。棋子一面为黑，一面为白。有一种操作叫做“翻转”，对某一枚棋子做“翻转”操作，则会将该棋子及其上下左右的 4 枚棋子翻过来。给定初始的棋盘局面（有的棋子黑面朝上，有的棋子白面朝上），求最少需要多少次操作，能使得所有棋子都白面朝上或黑面朝上。
样例输入
样例输出
思路
类似八数码 bfs搜就行
AC代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
| #include<cstring>
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<unordered_map>
#include<queue>
using namespace std;
const int N = 4;
string start;
queue<string> q;
unordered_map<string, int> dis;
int dx[5] = {0, 1,-1,0,0 }, dy[5] = { 0,0,0,1,-1 };
int bfs()
{
q.push(start);
dis[start] = 0;
while (!q.empty())
{
string t = q.front();
q.pop();
string str = t;
if (t.find('b')== t.npos || t.find('w')==t.npos)return dis[t];
for (int i = 0; i <= 15; i++)
{
int pos = i;
int x = pos / 4, y = pos % 4;
for (int j = 0; j <= 4; j++)
{
int xx = x + dx[j], yy = y + dy[j];
if (xx >= 0 && xx <= 3 && yy >= 0 && yy <= 3)
{
char t = str[xx * 4 + yy];
if (t == 'b')str[xx * 4 + yy] = 'w';
if (t == 'w')str[xx * 4 + yy] = 'b';
}
}
if (str != t&&!dis.count(str)) {
dis[str] = dis[t] + 1;
q.push(str);
}
}
}
cout << "Impossible";
return -1;
}
int main()
{
for (int i = 0; i <= 3; i++)
{
string c;
cin >> c;
start += c;
}
int t = bfs();
if (t == -1) cout << "Impossible";
if (t == 0)cout << "0";
if (t != -1 && t)cout << t;
return 0;
}
|