用户输出
4
1222
1424
3242
4344
系统信息
Exited with return code 0
编号 | 题目 | 状态 | 分数 | 总时间 | 内存 | 代码 / 答案文件 | 提交者 | 提交时间 |
---|---|---|---|---|---|---|---|---|
#6118 | #1045. mm逗黑白猫 | Accepted | 100 | 61 ms | 988 K | C++ / 2.3 K | lenijwp | 2019-06-28 20:58:20 |
#include <bits/stdc++.h>
using namespace std;
#define MAXN 66000
bool vis[MAXN];
int pre[MAXN];
int st_begin, st_end;
int que[MAXN], tail;
int dis[MAXN];
void Print(int x) {
cout << 1 + (x - 1) / 4;
cout << 1 + (x - 1) % 4;
}
void rebu(int x) {
cout << "staut = " << x << ":" << endl;
for (int i = 1; i <= 16; i++) {
if (x & (1 << (i - 1))) {
cout << "1";
} else {
cout << 0;
}
if (i % 4 == 0)
cout << endl;
}
}
void solve(int x) {
if (x == st_begin)
return;
solve(pre[x]);
int y = pre[x] ^ x;
int tmp = 1;
int pos = 1;
int xx = -1, yy = -1;
for (int i = 1; i <= 16; i++) {
if (y & tmp) {
if (xx < 0)
xx = pos;
else {
yy = pos;
break;
}
}
tmp <<= 1;
pos++;
}
if (xx > yy) {
int c = xx;
xx = yy;
yy = c;
}
Print(xx);
Print(yy);
cout << endl;
}
bool judge(int x, int y) {
for (int i = 0; i < 16; i++) {
if (x & (1 << i)) {
if ((y & (1 << i)) == 0) {
return 1;
}
} else {
if ((y & (1 << i)) != 0) {
return 0;
}
}
}
return 0;
}
int main() {
char c;
for (int i = 1; i <= 16; i++) {
cin >> c;
st_begin = (c - '0') * (1 << (i - 1)) + st_begin;
}
for (int i = 1; i <= 16; i++) {
cin >> c;
st_end = (c - '0') * (1 << (i - 1)) + st_end;
}
memset(pre, -1, sizeof(pre));
vis[st_begin] = 1;
que[++tail] = st_begin;
int cnt = 1;
int x, y;
while (tail <= cnt) {
x = que[tail];
// rebu(x);
// cout<<"dis = "<<dis[x]<<endl;
// cout<<x<<endl;
// system("pause");
tail++;
int ls = 2;
int rs = 1;
int us = 16;
int ds = 1;
for (int i = 1; i <= 15; i++) {
if (i % 4 == 0) {
ls <<= 1;
rs <<= 1;
if (i <= 12) {
y = x - (x & us) - (x & ds) + ((x & us) >> 4) + ((x & ds) << 4);
if (!vis[y]) {
vis[y] = 1;
pre[y] = x;
dis[y] = dis[x] + 1;
que[++cnt] = y;
}
us <<= 1;
ds <<= 1;
}
continue;
}
y = x - (x & ls) - (x & rs) + ((x & ls) >> 1) + ((x & rs) << 1);
if (!vis[y]) {
// cout<<(x&ls)<<endl<<(x&rs)<<endl;
// cout<<((x&ls)>>1)<<endl<<((x&rs)<<1)<<endl;
// rebu(y);
// system("pause");
if (!vis[y]) {
que[++cnt] = y;
}
vis[y] = 1;
pre[y] = x;
dis[y] = dis[x] + 1;
}
ls <<= 1;
rs <<= 1;
if (i > 12)
continue;
y = x - (x & us) - (x & ds) + ((x & us) >> 4) + ((x & ds) << 4);
if (!vis[y]) {
if (!vis[y]) {
que[++cnt] = y;
}
vis[y] = 1;
pre[y] = x;
dis[y] = dis[x] + 1;
}
us <<= 1;
ds <<= 1;
}
}
cout << dis[st_end] << endl;
solve(st_end);
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