这个题跟前的那个华容道的题差不多，我们需要用map记录string有没有走过，然后用bfs遍历，
把三排的图利用 / 和 % 变成一行的字符，当找到刚开始要的找的目标字符串的时候就返回他的map值
#include<iostream> #include<algorithm> #include<cstring> #include<queue> #include<map> using namespace std ; int d[4][2] = {{0,1},{0,-1},{1,0},{-1,0}}; queue<string> q ;//bfs string a ,b;//初始字符串，目标字符串 map<string,int> mp ;//用mp记录距离，已经变换过的次数 int bfs(){ while(!q.empty()){ string now = q.front() ; q.pop() ; if(now == b) return mp[now] ;//找到目标字符串就返回 int cnt1 = now.find('.') ;//找到‘.’在字符串的位置 int x = cnt1 / 3 , y = cnt1 % 3 ; for(int i = 0 ; i < 4 ; i ++){ int tx = x + d[i][0] , ty = y + d[i][1] ; if(tx<0||tx>=3||ty<0||ty>=3) continue ; int cnt2 = tx * 3 + ty ; string ts = now ; ts[cnt1] = now[cnt2] ; ts[cnt2] = '.' ; if(mp[ts]) continue ;//如果这个字符串已经被遍历过就继续循环 q.push(ts) ; mp[ts] = mp[now] + 1 ;//mp值加一 } } } int main(){ cin >> a >> b ; q.push(a) ; mp[a] = 0 ;//当初始状态的时候不用变换为0 cout << bfs() << endl ; return 0 ; }
