1 条题解
-
1
202507zj23周子祥 (周子祥) LV 8 @ 2025-03-28 21:01:18
#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