「Bzoj 1054」「HAOI2008」移动玩具 (BFS+状压判重)

Bzoj 1054
每个状态当做一个点，然后BFS
每次BFS在状态里找1然后遍历即可，判重就存一个16位的二进制就行了，而不需要哈希
二维数组转16位的二进制，16位的二进制转二维数组的方法具体实现看代码。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
struct data {int st, d;};
int gl[5][5];
int a[5][5];
char s[5];
bool vis[1 << 17];
int cura[5][5];
int getIntByArray() {
    int st = 0, ret = 0; 
    for (int i = 1; i <= 4; i++) 
    for (int j = 1; j <= 4; j++) ret += cura[i][j] * (1 << st), st++;
    return ret;
}
void getArrayByInt(int a) {
    int st = 0;
    for (int i = 1; i <= 4; i++) 
    for (int j = 1; j <= 4; j++) cura[i][j] = (a >> st) & 1, st++;
}
void clean() {
    ms(vis, false);
}
void solve() {
    clean();
    for (int i = 1; i <= 4; i++) {
        scanf("%s", s + 1);
        for (int j = 1; j <= 4; j++) {
            cura[i][j] = a[i][j] = s[j] - '0';
        }
    }
    for (int i = 1; i <= 4; i++) {
        scanf("%s", s + 1);
        for (int j = 1; j <= 4; j++) {
            gl[i][j] = s[j] - '0';
        }
    }
    queue<data> q;
    q.push((data){getIntByArray(), 0});

    for (int x = 1; x <= 4; x++)
    for (int y = 1; y <= 4; y++) cura[x][y] = gl[x][y];

    int gl_ = getIntByArray();

    while (!q.empty()) {
        data p = q.front(); q.pop();
        if (p.st == gl_) {
            printf("%d\n", p.d);
            return ;
        }
        getArrayByInt(p.st);
        int nowa[5][5];

        for (int x = 1; x <= 4; x++)
        for (int y = 1; y <= 4; y++) nowa[x][y] = cura[x][y];

        for (int x = 1; x <= 4; x++)
        for (int y = 1; y <= 4; y++)
        if (nowa[x][y] == 1)
        for (int i = 0; i < 4; i++) {
            int tx = x + dx[i], ty = y + dy[i];
            if (tx > 0 && ty > 0 && tx <= 4 && ty <= 4 && nowa[tx][ty] == 0) {
                swap(cura[x][y], cura[tx][ty]);
                int tt = getIntByArray();
                if (!vis[tt]) {
                    q.push((data){tt, p.d + 1});
                    vis[tt] = true;
                }
                swap(cura[x][y], cura[tx][ty]);
            }
        }
    }
}
int main() {
    #ifndef ONLINE_JUDGE 
    freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
    #endif
    solve();
    return 0;
}