資源限制

時間限制：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 0
	s.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;
}