LYDSY 1054

题目大意

暂无

题目解法

暂无

RTFC

#include <cctype>
#include <cstdio>
int s, t, que[1 << 16 | 1], vis[1 << 16 | 1], head, tail;
int a[4][4];
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, -1, 0, 1};
inline void unzip(int x)
{
    for (int i = 3; i >= 0; i--)
        for (int j = 3; j >= 0; j--)
            a[i][j] = x & 1, x >>= 1;
}
inline int zip()
{
    int ret = 0;
    for (int i = 0; i < 4; i++)
        for (int j = 0; j < 4; j++)
            ret = (ret << 1) | a[i][j];
    return ret;
}
int main()
{
    for (int i = 0, ch; i < 16; i++)
    {
        while (!isdigit(ch = getchar()))
            ;
        s = (s << 1) | (ch == '1');
    }
    for (int i = 0, ch; i < 16; i++)
    {
        while (!isdigit(ch = getchar()))
            ;
        t = (t << 1) | (ch == '1');
    }
    que[tail++] = s;
    for (int x, tmp; head ^ tail; head++)
    {
        x = que[head];
        if (x == t) break;
        unzip(x);
        for (int i = 0; i < 4; i++)
            for (int j = 0; j < 4; j++)
                if (a[i][j])
                    for (int d = 0; d < 4; d++)
                    {
                        i += dx[d], j += dy[d];
                        if (i >= 0 && i <= 3 && j >= 0 && j <= 3 && a[i][j] == 0)
                        {
                            a[i - dx[d]][j - dy[d]] = 0, a[i][j] = 1;
                            tmp = zip();
                            if (!vis[tmp]) vis[que[tail++] = tmp] = vis[x] + 1;
                            a[i - dx[d]][j - dy[d]] = 1, a[i][j] = 0;
                        }
                        i -= dx[d], j -= dy[d];
                    }
    }
    printf("%d", vis[t]);
    return 0;
}