UVA1063 Marble Game

题目传送门

说是题解其实是 debug 记（叹气）

显然 BFS，状态我是用 vector<vector<int>> 来存每个格子上的 Marble 编号，洞可以根据这个推出来，就不用存。

转移时，枚举向四个方向移动。这里写四个函数可能会比较烦，我的做法是，对于 $n\in [0,4]$，先将盘面顺时针转 $n\cdot 90^\circ$，再将所有 Marble 向左移动，最后将盘面顺时针旋转 $(4-n)\cdot 90^\circ$。

注意：

• 旋转时，Marble，洞和墙都要旋转。
• 移动时，如果 Marble 掉进了对应的洞里，就把这个 Marble 和洞都删掉，如果掉进了别人的洞里，就不进行这个方向的转移。
• 输出格式，impossible 首字母小写，如果答案是 1 仍然是 moves 而不是 move。

然后，我就 WA 啦。

找 gzy 的程序对拍了下，放一下生成数据的代码：

int a[5][5], b[5][5], cnt;
int x[16];
template <class T>
T randint(T l, T r = 0) {
    static mt19937 eng(time(0));
    if (l > r)
        swap(l, r);
    uniform_int_distribution<T> dis(l, r);
    return dis(eng);
}
int dx[] = { -1,0,0,1 };
int dy[] = { 0,-1,1,0 };
void solve() {
    rep(T, 1000) {
        rep(i, 16)x[i] = i;
        random_shuffle(x, x + 16);
        cnt = 0;
        rep(i, 4)rep(j, 4)a[i][j] = x[cnt++];
        rep(i, 16)x[i] = i;
        random_shuffle(x, x + 16);
        cnt = 0;
        rep(i, 4)rep(j, 4)b[i][j] = x[cnt++];
        int M = randint(1, 8), W = randint(0, 10);
        bool f = 0;
        rep(i, 4)rep(j, 4)if (a[i][j] < M && b[i][j] < M)f = 1;
        if (f == 1)continue;
        cout << 4 << ' ' << M << ' ' << W << endl;
        rep(s, M)
            rep(i, 4)rep(j, 4)if (a[i][j] == s)cout << i << ' ' << j << endl;
        rep(s, M)
            rep(i, 4)rep(j, 4)if (b[i][j] == s)cout << i << ' ' << j << endl;
        while (W--) {
            int A = randint(1, 2), B = randint(1, 2), C = randint(0, 3);
            cout << A << ' ' << B << ' ' << A + dx[C] << ' ' << B + dy[C] << endl;
        }
    }
    cout << "0 0 0\n";
}

拍出来几个问题：

• 输入数据中下标是从 0 开始的
• 多测记得清空
• 每次移动后，Marble 和洞都要还原成移动前的位置
• 记录每个 Marble 是否出现的数组要开至少 8 大小

拍出来问题的数据

Input 1

4 3 7
0 1
2 0
0 3
2 1
1 1
3 2
2 2 3 2
1 2 1 3
1 1 2 1
2 1 2 2
2 2 3 2
2 2 3 2
1 2 1 1

Output 1

impossible

Input 2

4 8 9
0 0
1 0
2 0
3 0
3 1
3 2
3 3
2 3
1 2
2 2
2 1
1 1
0 1
0 2
0 3
1 3
0 0 0 1
1 0 1 1
2 0 2 1
2 1 3 1
2 2 3 2
2 2 2 3
1 2 1 3
0 2 1 2
1 1 1 2

Output 2

25 moves

Code

int n, m, w, A, B, C, D;
bool operator<(vector<vector<int>> A, vector<vector<int>> B) {
    repp(i, n)repp(j, n)if (A[i][j] != B[i][j])return A[i][j] < B[i][j];
    return 0;
}
bool operator==(vector<vector<int>> A, vector<vector<int>> B) {
    repp(i, n)repp(j, n)if (A[i][j] != B[i][j])return 0;
    return 1;
}
vector<vector<int>> a(5), b(5), x(5), y(5), cpy(5);
bool f[5][5][5][5], f_[5][5][5][5], F[100];
map<vector<vector<int>>, int>vis;
void rotate(int N) {
    while (N--) {
        repp(i, n)repp(j, n)cpy[i][j] = x[n + 1 - j][i];
        x = cpy;
        repp(i, n)repp(j, n)cpy[i][j] = y[n + 1 - j][i];
        y = cpy;
        repp(i1, n)repp(j_1, n)repp(i2, n)repp(j2, n)f_[i1][j_1][i2][j2] = f[n + 1 - j_1][i1][n + 1 - j2][i2];
        repp(i1, n)repp(j_1, n)repp(i2, n)repp(j2, n)f[i1][j_1][i2][j2] = f_[i1][j_1][i2][j2];
    }
}
bool move() {
    repp(i, n) {
        repp(j, n) {
            if (!x[i][j])continue;
            int k = j;
            while (k > 1 && !f[i][k - 1][i][k] && !x[i][k - 1]) {
                x[i][k - 1] = x[i][k];
                x[i][k] = 0;
                k--;
                if (y[i][k] == x[i][k]) {
                    x[i][k] = y[i][k] = 0;
                    break;
                }
                if (y[i][k] && y[i][k] != x[i][k])return 0;
            }
        }
    }
    return 1;
}
int bfs() {
    queue<pair<vector<vector<int>>, int>>q;
    q.push(mp(a, 0));
    vis[a] = T_;
    while (!q.empty()) {
        x = q.front().fi;
        int val = q.front().se;
        q.pop();
        init(F, 0);
        bool tmp = 0;
        repp(i, n)repp(j, n)if (x[i][j])F[x[i][j]] = tmp = 1;
        if (!tmp)return val;
        repp(i, n)repp(j, n) {
            if (F[b[i][j]])y[i][j] = b[i][j];
            else y[i][j] = 0;
        }
        vector<vector<int>>xx = x, yy = y;
        bool suc;
        suc = move();
        if (suc && vis[x] != T_)q.push(mp(x, val + 1)), vis[x] = T_;
        x = xx, y = yy;
        rotate(1);
        suc = move();
        rotate(3);
        if (suc && vis[x] != T_)q.push(mp(x, val + 1)), vis[x] = T_;
        x = xx, y = yy;
        rotate(2);
        suc = move();
        rotate(2);
        if (suc && vis[x] != T_)q.push(mp(x, val + 1)), vis[x] = T_;
        x = xx, y = yy;
        rotate(3);
        suc = move();
        rotate(1);
        if (suc && vis[x] != T_)q.push(mp(x, val + 1)), vis[x] = T_;
    }
    return -1;
}
void solve() {
    repp(i, n)a[i].resize(5), b[i].resize(5), x[i].resize(5), y[i].resize(5), cpy[i].resize(5);
    repp(i, n)repp(j, n)a[i][j] = b[i][j] = 0;
    repp(i, n)repp(j, n)repp(ii, n)repp(jj, n)f[i][j][ii][jj] = 0;
    repp(i, m) {
        cin >> A >> B;
        a[A + 1][B + 1] = i;
    }
    repp(i, m) {
        cin >> A >> B;
        b[A + 1][B + 1] = i;
    }
    repp(i, w) {
        cin >> A >> B >> C >> D;
        A++, B++, C++, D++;
        f[A][B][C][D] = f[C][D][A][B] = 1;
    }
    int ans = bfs();
    if (ans == -1) cout << "Case " << T_ << ": impossible\n\n";
    else cout << "Case " << T_ << ": " << ans << " moves\n\n";
}