問題描述
如下面第一個圖的九宮格中，放着 1~8 的數字卡片，還有一個格子空着。與空格子相鄰的格子中的卡片可以移動到空格中。經過若幹次移動，可以形成第二個圖所示的局面。
我們把第一個圖的局面記為：12345678.
把第二個圖的局面記為：123.46758
顯然是按從上到下，從左到右的順序記錄數字，空格記為句點。
本題目的任務是已知九宮的初态和終态，求最少經過多少步的移動可以到達。如果無論多少步都無法到達，則輸出-1。
輸入格式
輸入第一行包含九宮的初态，第二行包含九宮的終态。
輸出格式
輸出最少的步數，如果不存在方案，則輸出-1。
樣例輸入
12345678.
123.46758
樣例輸出
3
樣例輸入
13524678.
46758123.
樣例輸出
22
狀态之間的轉移，運用雙向廣度優先搜尋
雙向廣度優先搜尋比一般的廣搜要快，因為會減少大量狀态的周遊，從起點和終點同時進行廣搜，每次選擇小的隊列搜尋，使用不同的标記，區分未出現過得狀态和分别出現在兩個隊列中的狀态。
#include<iostream>
#include<queue>
#include<map>
using namespace std;
string source;
string result;
int nex[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
map<string, int> known;//判斷該狀态是否出現過，以及在哪個隊列出現過
map<string, int> level;//記錄節點的層次
string swap(string temp, int x, int y)
{
string str = temp;
char c = str[x];
str[x] = str[y];
str[y] = c;
return str;
}
int dbfs()
{
if(source == result)
return 0;
queue<string> q1, q2;
q1.push(source);
q2.push(result);
known[source] = 1;
known[result] = 2;
while(!q1.empty() && !q2.empty())
{
string front;
int flag;
if(q1.size() < q2.size())
{
front = q1.front();
q1.pop();
flag = 1;
}
else{
front = q2.front();
q2.pop();
flag = 2;
}
int dot = front.find('.');
int x = dot / 3; //對應九宮格中的行
int y = dot % 3;//對應九宮格中的列
for(int k = 0;k < 4;k++)
{
int nextx = x + nex[k][0];
int nexty = y + nex[k][1];
if(nextx >= 0 && nextx < 3 && nexty >= 0 && nexty < 3)
{
int nextPos = nextx*3 + nexty;
string now = swap(front, dot, nextPos);//獲得新的狀态
if(known[front] + known[now] == 3)//相遇
{
return level[front] + level[now] + 1;
}
else
{
if(known[now] == 0)//該狀态之前未曾遇到過
{
if(flag == 1)
{
q1.push(now);
}
else{
q2.push(now);
}
known[now] = known[front];
level[now] = level[front] + 1;
}
}
}
}
}
return -1;
}
int main(void)
{
cin >> source >> result;
cout << dbfs();
return 0;
}