问题描述
如下面第一个图的九宫格中，放着 1~8 的数字卡片，还有一个格子空着。与空格子相邻的格子中的卡片可以移动到空格中。经过若干次移动，可以形成第二个图所示的局面。
我们把第一个图的局面记为：12345678.
把第二个图的局面记为：123.46758
显然是按从上到下，从左到右的顺序记录数字，空格记为句点。
本题目的任务是已知九宫的初态和终态，求最少经过多少步的移动可以到达。如果无论多少步都无法到达，则输出-1。
我们把第一个图的局面记为：12345678.
把第二个图的局面记为：123.46758
显然是按从上到下，从左到右的顺序记录数字，空格记为句点。
本题目的任务是已知九宫的初态和终态，求最少经过多少步的移动可以到达。如果无论多少步都无法到达，则输出-1。
输入格式
输入第一行包含九宫的初态，第二行包含九宫的终态。
输出格式
输出最少的步数，如果不存在方案，则输出-1。
样例输入
12345678.
123.46758
123.46758
样例输出
3
样例输入
13524678.
46758123.
46758123.
样例输出
22
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#define N 20005
using namespace std;
char mp[3][3], gp[3][3];
int dir[4][2] = {0,1, 1,0, -1,0, 0,-1};
char str[10];
struct node{
int x, y;
int step;
char cur_mp[3][3];//记录当前图案
node(){
}
node(int x, int y, int step){
this->x = x;
this->y = y;
this->step = step;
}
};
set<int>st;
queue<node>q;
bool check(node cur){
for(int i=0; i<3; ++i)
for(int j=0; j<3; ++j)
if(cur.cur_mp[i][j] != gp[i][j])
return false;
return true;
}
int cal(node cur){//每一次移动将会映射到一个不同的整数
int ss = 0;
for(int i=0; i<3; ++i)
for(int j=0; j<3; ++j)
if(cur.cur_mp[i][j] != '.')
ss = ss*10+(cur.cur_mp[i][j]-'0');
else ss = ss*10+9;
return ss;
}
void bfs(){
st.clear();
if(!q.empty())
st.insert(cal(q.front()));
while(!q.empty()){
node cur = q.front();
q.pop();
if(check(cur)) {
cout<<cur.step<<endl;
return ;
}
for(int i=0; i<4; ++i){
int xx = cur.x+dir[i][1];
int yy = cur.y+dir[i][0];
if(xx<0 || xx>2 || yy<0 || yy>2) continue;
node nt = node(xx, yy, cur.step+1);
memcpy(nt.cur_mp, cur.cur_mp, sizeof(cur.cur_mp));
nt.cur_mp[cur.x][cur.y]^=nt.cur_mp[xx][yy];
nt.cur_mp[xx][yy]^=nt.cur_mp[cur.x][cur.y];
nt.cur_mp[cur.x][cur.y]^=nt.cur_mp[xx][yy];
int val = cal(nt);
if(st.find(val) != st.end()) continue;
st.insert(val);
q.push(nt);
}
}
cout<<-1<<endl;
}
int main() {
while(cin>>str){
int bx, by;
while(!q.empty()) q.pop();
int len = 0;
for(int i=0; i<3; ++i)
for(int j=0; j<3; ++j){
mp[i][j] = str[len++];
if(mp[i][j] == '.') bx=i, by=j;
}
node cur = node(bx, by, 0);
memcpy(cur.cur_mp, mp, sizeof(mp));
q.push(cur);
cin>>str;
len = 0;
for(int i=0; i<3; ++i)
for(int j=0; j<3; ++j)
gp[i][j] = str[len++];
bfs();
}
return 0;
}
