Solution

直接搜索就可以了。可以状压一下方便判重。

Code

#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
int s, t;
int a[10][10];
int toNum() {
    int x = 0;
    for(int i=1; i<=4; i++)
    for(int j=1; j<=4; j++) {
        x <<= 1;
        x |= a[i][j];
    }
    return x;
}
void toArr(int x) {
    for(int i=4; i; i--)
    for(int j=4; j; j--, x>>=1)
        a[i][j] = x & 1;
}
queue<int> q;
bool used[1<<18];
int d[1<<18];
int go[4][2] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
bool check(int x, int y) {
    return x >= 1 && x <= 4 && y >= 1 && y <= 4;
}
void bfs() {
    q.push(s); used[s] = true;
    while(!q.empty()) {
        int u = q.front(); q.pop(); toArr(u);
        if(u == t) {
            printf("%d\n", d[t]);
            return;
        }
        for(int i=1; i<=4; i++) {
            for(int j=1; j<=4; j++) {
                if(!a[i][j]) continue;
                for(int k=0; k<4; k++) {
                    int tx = i + go[k][0];
                    int ty = j + go[k][1];
                    if(!check(tx, ty) || a[tx][ty]) continue;
                    swap(a[i][j], a[tx][ty]);
                    int v = toNum();
                    swap(a[i][j], a[tx][ty]);
                    if(used[v]) continue;
                    used[v] = true;
                    d[v] = d[u] + 1;
                    q.push(v);
                }
            }
        }
    }
}
char str[100];
int main() {
    for(int i=1; i<=4; i++) {
        scanf("%s", str+1);
        for(int j=1; j<=4; j++)
            a[i][j] = str[j] - '0';
    }
    s = toNum();
    for(int i=1; i<=4; i++) {
        scanf("%s", str+1);
        for(int j=1; j<=4; j++)
            a[i][j] = str[j] - '0';
    }
    t = toNum();
    bfs();
    return 0;
}

Description

在一个4*4的方框内摆放了若干个相同的玩具,某人想将这些玩具重新摆放成为他心中理想的状态,规定移动
时只能将玩具向上下左右四个方向移动,并且移动的位置不能有玩具,请你用最少的移动次数将初始的玩具状态移
动到某人心中的目标状态。

Input

前4行表示玩具的初始状态,每行4个数字1或0,1表示方格中放置了玩具,0表示没有放置玩具。接着是一个空
行。接下来4行表示玩具的目标状态,每行4个数字1或0,意义同上。

Output

一个整数,所需要的最少移动次数。

Sample Input

1111
0000
1110
0010

1010
0101
1010
0101

Sample Output

4