小 Z 开锁(Unlocking the Lock) 题解

思路分析

按题目要求使用对应数据结构与算法模拟/递推求解，注意数据范围边界与时间复杂度。

参考代码

#include <iostream>
#include <vector>
#include <string>
#include <queue>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int start = 0, target = 0;
    for (int i = 0; i < 4; ++i) {
        string s;
        if (!(cin >> s)) return 0;
        for (int j = 0; j < 4; ++j) {
            if (s[j] == '1') start |= (1 << (i * 4 + j));
        }
    }
    for (int i = 0; i < 4; ++i) {
        string s;
        cin >> s;
        for (int j = 0; j < 4; ++j) {
            if (s[j] == '1') target |= (1 << (i * 4 + j));
        }
    }
    vector<int> dist(1 << 16, -1);
    queue<int> q;
    dist[start] = 0;
    q.push(start);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        if (u == target) {
            cout << dist[u] << "\n";
            return 0;
        }
        for (int r = 0; r < 4; ++r) {
            for (int c = 0; c < 4; ++c) {
                int i = r * 4 + c;
                if (c + 1 < 4) {
                    int j = i + 1;
                    if (((u >> i) & 1) != ((u >> j) & 1)) {
                        int v = u ^ (1 << i) ^ (1 << j);
                        if (dist[v] == -1) {
                            dist[v] = dist[u] + 1;
                            q.push(v);
                        }
                    }
                }
                if (r + 1 < 4) {
                    int j = i + 4;
                    if (((u >> i) & 1) != ((u >> j) & 1)) {
                        int v = u ^ (1 << i) ^ (1 << j);
                        if (dist[v] == -1) {
                            dist[v] = dist[u] + 1;
                            q.push(v);
                        }
                    }
                }
            }
        }
    }
    cout << 0 << "\n";
    return 0;
}