1 条题解

  • 1

    #include <iostream>
    #include <queue>
    #include <map>
    using namespace std;

    int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};

    struct matrix {
    int arr[4][4];
    bool operator < (const matrix &other) const {
    for (int i = 0; i < 4; i++)
    for (int j = 0; j < 4; j++) {
    if (arr[i][j] < other.arr[i][j])
    return true;
    if (arr[i][j] > other.arr[i][j])
    return false;
    }
    return false;
    }
    };

    int main() {
    matrix start, _end;
    for (int i = 0; i < 4; i++) {
    string input;
    cin >> input;
    for (int j = 0; j < 4; j++)
    start.arr[i][j] = input[j] - '0';
    }
    for (int i = 0; i < 4; i++) {
    string input;
    cin >> input;
    for (int j = 0; j < 4; j++)
    _end.arr[i][j] = input[j] - '0';
    }
    queue<matrix> que;
    map<matrix, int> steps;
    que.push(start);
    steps[start] = 0;
    while (!que.empty() && steps.find(_end) == steps.end()) {
    matrix front = que.front();
    que.pop();
    for (int x0 = 0; x0 < 4; x0++)
    for (int y0 = 0; y0 < 4; y0++)
    for (int i = 0; i < 4; i++) {
    int x = x0 + dx[i];
    int y = y0 + dy[i];
    if (x >= 0 && x < 4 && y >= 0 && y < 4) {
    matrix push = front;
    swap(push.arr[x0][y0], push.arr[x][y]);
    if (steps.find(push) == steps.end()) {
    que.push(push);
    steps[push] = steps[front] + 1;
    }
    }
    }
    }
    cout << steps[_end] << endl;
    return 0;
    }

  • 1

信息

ID
1180
难度
9
分类
搜索 | 搜索与剪枝 点击显示
标签
递交数
6
已通过
6
通过率
100%
上传者