#include<iostream>
#include<queue>
#include <unordered_map>
using namespace std ;
int bfs(string x)
{
queue <string> q ;
q.push(x) ;
unordered_map<string, int> d ; //距离记录哈希表
d[x] = 0 ;
int dx[4] = {1 , - 1 , 0 , 0} , dy[4] = {0 , 0 , 1 , - 1} ;
string end = "12345678x" ;
while(!q.empty())
{
string start = q.front() ;
q.pop() ;
if(start == end)
return d[start] ;
int k = start.find('x') ;
int x = k / 3 , y = k % 3 ;
int dis = d[start] ;
for(int i = 0 ; i < 4 ; i ++)
{
int x1 = x + dx[i] , y1 = y + dy[i] ;
if(x1 >= 0 && x1 < 3 && y1 >= 0 && y1 < 3)
{
swap(start[k] , start[x1 * 3 + y1]) ;
if(!d.count(start)) //判断是否访问过该点
{
q.push(start) ;
d[start] = dis + 1 ;
}
swap(start[k] , start[x1 * 3 + y1]) ;
}
}
}
return -1 ;
}
int main()
{
string s ;
for(int i = 0 ; i < 9 ; i ++)
{
char s1 ;
cin >> s1 ;
s += s1 ;
}
cout << bfs(s) ;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla