如何自建一个便宜的网站/成都网站推广经理

资源限制

时间限制：1.0s 内存限制：256.0MB

问题描述

如下面第一个图的九宫格中，放着 1~8 的数字卡片，还有一个格子空着。与空格子相邻的格子中的卡片可以移动到空格中。经过若干次移动，可以形成第二个图所示的局面。

我们把第一个图的局面记为：12345678.
把第二个图的局面记为：123.46758
显然是按从上到下，从左到右的顺序记录数字，空格记为句点。
本题目的任务是已知九宫的初态和终态，求最少经过多少步的移动可以到达。如果无论多少步都无法到达，则输出-1。

输入格式

输入第一行包含九宫的初态，第二行包含九宫的终态。

输出格式

输出最少的步数，如果不存在方案，则输出-1。

样例输入

样例输出

3

样例输入

样例输出

22

---

思路：

思路来自紫书P199页，一毛一样的题目。

通过BFS求最短路，第一次出现与目标九宫格相同时，就是最少的步数

把九宫格的状态通过数组记录下来，记录过程中需要判重，避免把同种情况的九宫格访问多次。

判重：将九宫格变化为一个九位数放入集合中（集合中没有才放入）。

看书上说集合这种方法虽然简单，但是效率最慢，以后有需要在学习其他几种方法。

memcmp

memcpy

代码：

#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
#include <cstring>
#include <cmath>
#include <vector>
#include <set>
#include <map>
using namespace std;
typedef int state[9];
string s1,s2;
const int maxn=362900;  //最大情况9！=362880
state st[maxn],goal; //存过程的二维数组和目标数组，st相当于st[maxn][9]
set<int> s;  //集合
int dis[maxn];  //距离
int dx[]={0,0,1,-1};  //四个方向
int dy[]={1,-1,0,0};void init() {s.clear();}  //初始化集合
bool insert(int rear)   //插入集合
{int v=0;for(int i=0;i<9;i++) v=v*10+st[rear][i]; //九宫格转变为九位数if(s.count(v)>0) return 0;  //s中有相同的，return 0s.insert(v);return 1;
}int bfs()
{init();int front=1,rear=2; //如果要从0开始，最后可以用return -1表示不存在while(front<rear){state& f = st[front]; //引用if(memcmp(goal,f,sizeof(f))==0) return front; //比较数组int z;for(z=0;z<9;z++) if(!f[z]) break; //找0的位置int x=z/3,y=z%3;    //行列编号for(int i=0;i<4;i++){int newx=x+dx[i];int newy=y+dy[i];int newz=3*newx+newy; //在一维数组中的下标if(newx>=0&&newx<3&&newy>=0&&newy<3){state& r= st[rear];  //引用memcpy(r,f,sizeof(f)); //扩展新节点(先和上一个状态一样)r[newz]=f[z];  //然后改变移动以后，变化的两个点r[z]=f[newz];dis[rear]=dis[front]+1;  //更新步数if(insert(rear)) rear++; //插入成功，队尾往后移}}front++;  //扩展完毕后修改队首指针}return 0;   //不存在
}int main() 
{getline(cin,s1);  //字符串输入，再转化为int数组getline(cin,s2); for(int i=0;i<9;i++) {if(s1[i]=='.') st[1][i]=0;  //起始状态else st[1][i]=s1[i]-'0';   if(s2[i]=='.') goal[i]=0;   //目标状态else goal[i]=s2[i]-'0';}int ans = bfs();if(!ans) cout<<-1;  else cout<<dis[ans];return 0;
}