用户输出
4
1222
1424
3242
4344
系统信息
Exited with return code 0
编号 | 题目 | 状态 | 分数 | 总时间 | 内存 | 代码 / 答案文件 | 提交者 | 提交时间 |
---|---|---|---|---|---|---|---|---|
#5945 | #1045. mm逗黑白猫 | Accepted | 100 | 143 ms | 2444 K | C++ 11 / 2.2 K | Akatsuki | 2019-06-28 16:06:43 |
#include <cstdio>
#include <iostream>
#include <deque>
using namespace std;
struct huan {
int x1, x2, y1, y2;
};
struct map {
int s[6][6];
deque<huan> ans;
};
deque<map> maps;
int f[66000], aim;
map qi, a;
int zhuan() {
int i, j, ans = 0, t = 1;
for (i = 1; i <= 4; i++) {
ans += t * (a.s[i][1] * 8 + a.s[i][2] * 4 + a.s[i][3] * 2 + a.s[i][4]);
t *= 16;
}
return ans;
}
void print() {
int i, n = a.ans.size();
printf("%d\n", n);
for (i = 0; i < n; i++) printf("%d%d%d%d\n", a.ans[i].x1, a.ans[i].y1, a.ans[i].x2, a.ans[i].y2);
}
void bfs() {
int i, j, k, n, w;
huan t;
while (1) {
n = maps.size();
for (k = 0; k < n; k++) {
for (i = 1; i <= 4; i++)
for (j = 1; j <= 4; j++) {
if (i < 4) {
a = maps[0];
t.x1 = i;
t.y1 = j;
t.x2 = i + 1;
t.y2 = j;
a.ans.push_back(t);
w = a.s[i][j];
a.s[i][j] = a.s[i + 1][j];
a.s[i + 1][j] = w;
w = zhuan();
if (w == aim) {
print();
return;
}
if (f[w] == 0) {
f[w] = 1;
maps.push_back(a);
}
}
if (j < 4) {
a = maps[0];
t.x1 = i;
t.y1 = j;
t.x2 = i;
t.y2 = j + 1;
a.ans.push_back(t);
w = a.s[i][j];
a.s[i][j] = a.s[i][j + 1];
a.s[i][j + 1] = w;
w = zhuan();
if (w == aim) {
print();
return;
}
if (f[w] == 0) {
f[w] = 1;
maps.push_back(a);
}
}
}
maps.pop_front();
}
}
}
int main() {
int i, t = 1;
char s[6];
for (i = 1; i <= 4; i++) {
scanf("%s", s + 1);
qi.s[i][1] = s[1] - 48;
qi.s[i][2] = s[2] - 48;
qi.s[i][3] = s[3] - 48;
qi.s[i][4] = s[4] - 48;
}
for (i = 1; i <= 4; i++) {
scanf("%s", s + 1);
aim += t * ((s[1] - 48) * 8 + (s[2] - 48) * 4 + (s[3] - 48) * 2 + s[4] - 48);
t *= 16;
}
maps.push_back(qi);
bfs();
return 0;
}
用户输出
4
1222
1424
3242
4344
系统信息
Exited with return code 0
用户输出
3
1323
3242
2232
系统信息
Exited with return code 0
用户输出
6
1112
1314
1323
2333
3132
4142
系统信息
Exited with return code 0
用户输出
9
1213
1112
1314
1213
2232
2223
2434
3343
3444
系统信息
Exited with return code 0
用户输出
11
1112
1323
2131
1121
2232
2333
2324
3141
3132
3343
2333
系统信息
Exited with return code 0
用户输出
7
2131
2122
2333
1323
1314
3141
3132
系统信息
Exited with return code 0
用户输出
15
1213
1112
1314
2333
2223
2122
2434
1424
3141
3242
2232
3343
2333
3444
2434
系统信息
Exited with return code 0
用户输出
14
1424
1314
1213
1112
2232
1222
2333
2223
2434
3141
3242
3343
2333
3444
系统信息
Exited with return code 0
用户输出
10
1121
2223
2122
2333
2434
3141
3242
3343
4344
4243
系统信息
Exited with return code 0