这个题跟跳蚱蜢那个题一摸一样用map判重就行了 希望今年也能出类似的题
#include<iostream> #include<cstring> #include<algorithm> #include<map> #include<queue> using namespace std ; struct node{ string s ; int t ; node(string ss ,int tt) { s = ss , t = tt ; } }; string st1 , st2 ; queue<node> q; map<string,bool> mp ; void bfs(){ while(!q.empty()){ node now = q.front() ; q.pop() ; if(now.s == st2) { cout << now.t << endl ; break ; } int i ; for(i = 0 ; i < st1.size(); i ++){ if(now.s[i] == '*') break ; } for(int j = i-3 ; j <= i +3 ; j ++){ if(j < 0 || j >= st1.size() || i == j) continue ; string ss = now.s ; char tmp = ss[i]; ss[i] = ss[j] ; ss[j] = tmp ; if(mp[ss]) continue ; else { mp[ss] = true ; q.push(node(ss,now.t + 1)) ; } } } } int main(){ cin >> st1 >> st2 ; // cout << st1 << endl << st2 << endl ; q.push(node(st1,0)) ; mp[st1] = true; bfs(); return 0 ; }