这个题用bfs搜索，让空格走，找到最终关羽和张飞的位置与他们两个原来的位置相同，
这个可以用map来判重，并用来记录距离，map<string,int> ，用来记录走到s这种情况需要的最短步数，
#include<iostream> #include<algorithm> #include<cstring> #include<map> #include<queue> using namespace std ; string s ; queue<string> q ;//队列用来bfs ，每种string记录当前图里的情况 map<string,int> mp ;//走到s这样的情况时，走的步数 int d[4][2] = {{1,0},{-1,0},{0,1},{0,-1}} ; int a , b ; //记录刚开始张飞和关羽的位置 void bfs(){ q.push(s) ; mp[s] = 0 ;//原始情况不用走就是0 while(!q.empty()){ string now = q.front() ; q.pop() ; int c = now.find('A') , e = now.find('B') ; if(c == b && e == a){//找到他们的位置相同就进行输出答案 cout << mp[now] << endl ; return ; } int pos1 = now.find(' ') ;//找到空格的位置，让空格走 int x = pos1/3 , y = pos1%3 ; for(int i = 0 ; i < 4 ; i ++){ int tx = x + d[i][0] , ty = y + d[i][1] ; if(tx < 0 || tx >= 2 || ty < 0 || ty >= 3) continue ;//越界 int pos2 = tx * 3 + ty ; //二维变成一维处理 string ss = now ; ss[pos1] = ss[pos2] ; ss[pos2] = ' ' ; //交换位置 if(mp[ss] == 0){//如果没有过这种情况，就压入队列中 mp[ss] = mp[now] + 1 ; q.push(ss) ; } } } } int main(){ string x ; for(int i = 0 ; i < 2 ; i ++){ getline(cin,x) ; s += x ;//变成一维 } a = s.find('A') ;//cout << a << endl ; b = s.find('B') ;//cout << b << endl ; bfs() ; return 0 ; }
