简答题
偏难
#7250
玩具摆放 在一个4*4的方框内摆放了若干个相同的玩具。 某人想通过移动玩具,将这些玩具重新摆放成为他心中理想的状态。要求每次移动时,只能将某一个玩具向上下左右四…
玩具摆放
在一个4*4的方框内摆放了若干个相同的玩具。
某人想通过移动玩具,将这些玩具重新摆放成为他心中理想的状态。要求每次移动时,只能将某一个玩具向上下左右四个方向之一移动一步。不能将玩具移出方框,并且移动的目标位置不能已经放置有玩具。
请你用最少的移动次数将初始的玩具状态移动到他心中的目标状态。
时间限制:10000
内存限制:524288
输入
前4行表示玩具的初始状态,每行4个数字1或0,1表示方格中放置了玩具,0表示没有放置玩具。 接着是一个空行。接下来4行表示玩具的目标状态,每行4个数字1或0,意义同上。
输出
一个整数,所需要的最少移动次数。保证初始状态可以达到目标状态。
样例输入
1111 0000 1110 0010 1010 0101 1010 0101
样例输出
4
提示
可以考虑将玩具局面表示为一个16 bit的整数,设置一个标志数组用来判重,用这个整数做下标找其对应标志位
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
// #include<cmath>
using namespace std;
const int INF = 9999999;
#define LL long long
inline int read() {
int x = 0, f = 1;
char c = getchar();
for (; !isdigit(c); c = getchar())
if (c == '-')
f = -1;
for (; isdigit(c); c = getchar())
x = x * 10 + c - '0';
return x * f;
}
int N, E;
bool vis[65539];
char c;
int l = 1, r = 1;
struct data {
int st, k;
} Que[700001];
void BFS() {
Que[l].st = 0, Que[l].k = N;
int step, Now;
if (Que[l].k == E) {
printf("%d", Que[l].st);
return;
}
while (l <= r) {
Now = Que[l].k, step = Que[l].st;
for (int i = 1; i <= 4; i++) {
for (int j = 1; j <= 4; j++) {
if (((Now >> ((4 - i) * 4 + 4 - j)) & 1)) {
for (int p = 0; p < 4; p++) {
if (p == 0 && i != 1 &&
!((Now >> ((4 - (i - 1)) * 4 + 4 - j)) & 1) &&
!vis[Now - (1 << ((4 - i) * 4 + 4 - j)) +
(1 << ((4 - i) * 4 + 8 - j))]) {
Que[++r].k = Now - (1 << ((4 - i) * 4 + 4 - j)) +
(1 << ((4 - i) * 4 + 8 - j));
if (Que[r].k == E) {
printf("%d", step + 1);
return;
}
Que[r].st = step + 1;
vis[Que[r].k] = 1;
}
if (p == 1 && i != 4 &&
!((Now >> ((4 - (i + 1)) * 4 + 4 - j)) & 1) &&
!vis[Now - (1 << ((4 - i) * 4 + 4 - j)) +
(1 << ((4 - i) * 4 - j))]) {
Que[++r].k =
Now - (1 << ((4 - i) * 4 + 4 - j)) + (1 << ((4 - i) * 4 - j));
if (Que[r].k == E) {
printf("%d", step + 1);
return;
}
Que[r].st = step + 1;
vis[Que[r].k] = 1;
}
if (p == 2 && j != 1 &&
!((Now >> ((4 - i) * 4 + 4 - (j - 1))) & 1) &&
!vis[(1 << ((4 - i) * 4 + 4 - j)) +
(1 << ((4 - i) * 4 + 4 - (j - 1)))]) {
Que[++r].k = Now - (1 << ((4 - i) * 4 + 4 - j)) +
(1 << ((4 - i) * 4 + 4 - (j - 1)));
if (Que[r].k == E) {
printf("%d", step + 1);
return;
}
Que[r].st = step + 1;
vis[Que[r].k] = 1;
}
if (p == 3 && j != 4 &&
!((Now >> ((4 - i) * 4 + 4 - (j + 1))) & 1) &&
!vis[Now - (1 << ((4 - i) * 4 + 4 - j)) +
(1 << ((4 - i) * 4 + 4 - (j + 1)))]) {
Que[++r].k = Now - (1 << ((4 - i) * 4 + 4 - j)) +
(1 << ((4 - i) * 4 + 4 - (j + 1)));
if (Que[r].k == E) {
printf("%d", step + 1);
return;
}
Que[r].st = step + 1;
vis[Que[r].k] = 1;
}
}
}
}
}
l++;
}
}
int main() {
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
int tmp = 16;
for (int i = 1; i <= 4; i++)
for (int j = 1; j <= 4; j++) {
cin >> c;
N = N + (1 << (tmp - 1)) * (c - '0');
tmp--;
}
vis[N] = true;
tmp = 16;
for (int i = 1; i <= 4; i++)
for (int j = 1; j <= 4; j++) {
cin >> c;
E = E + (1 << (tmp - 1)) * (c - '0');
tmp--;
}
BFS();
return 0;
}</pre>
这道题暂未补解析。