题目连接
#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<iostream>
#include<queue>
#include<cmath>
#include<set>
#include<cstring>
using namespace std;
char s[4][4], e[4][4];
char a[10];
struct point {
int x, y;
char status[4][4];
int cnt = 0;
point() {
};
point(int x, int y, char s[4][4] , int cnt) {
this->x = x; this->y = y;
for (int i = 0; i<3; i++)
for (int j = 0; j<3; j++) {
this->status[i][j] = s[i][j];
}
this->cnt = cnt;
}
}p;
int ll;
int dx[4] = { 0,1,0,-1 };
int dy[4] = { -1,0,1,0 };
bool is_ok(int x, int y) {
if (x<0 || x>2 || y<0 || y>2)return false;
return true;
}
bool check(char(*s)[4], char(*e)[4]) {
for (int i = 0; i<3; i++)
for (int j = 0; j<3; j++) {
if (s[i][j] != e[i][j])return false;
}
return true;
}
queue<point>que;
set<int>vis;
bool change(char (*s)[4]) {
int ans = 0;
for (int i = 0; i < 3; i++)
for(int j=0;j<3;j++){
if (s[i][j] == '.')ans = ans * 10;
else ans = ans * 10 + s[i][j] - '0';
}
if (vis.count(ans)) //容器中有相同
{
return 0;
}
vis.insert(ans);//插入容器
return 1;
}
void bfs() {
char temp[4][4];
while (!que.empty()) {
p = que.front();
que.pop();
if (check(p.status,e)) {
cout << p.cnt << endl;
return;
}
for (int i = 0; i<4; i++) {
int x = p.x + dx[i];
int y = p.y + dy[i];
if (is_ok(x, y)) {
memcpy(temp, p.status,sizeof(temp));
temp[p.x][p.y] = temp[x][y];
temp[x][y] = '.';
if (change(temp)) {
que.push(point(x, y, temp, p.cnt + 1));
}
}
}
}
}
int main() {
scanf("%s", a);
int c = 0;
int dxx, dyy;
for (int i = 0; i<3; i++)
for (int j = 0; j<3; j++) {
if (a[c] == '.') {
dxx = i, dyy= j;
}
s[i][j] = a[c++];
}
que.push(point(dxx, dyy, s, 0));
change(s);
c = 0;
scanf("%s", a);
for (int i = 0; i<3; i++)
for (int j = 0; j<3; j++) {
e[i][j] = a[c++];
}
bfs();
return 0;
}