题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include <bits/stdc++.h>
using namespace std;
string fir,en,no,nex;
int apo,bpo;
int dx[] = {0,-1,0,1};
int dy[] = {-1,0,1,0};
int bfs(){
    queue<string> q;//第一，创建queue，储存string
    unordered_map<string,int> mp;//第二，创建unordered_map,用string 储存int;
    q.push(fir);//第三，queue入队首节点。
    mp[fir] = 0; 
    while(!q.empty()){//while循环展开
        no = q.front();//now = front;
        q.pop();    //出队pop; 
        for(int i = 0;i<4;i++){
            nex = no;// for循环根据now节点产生next节点，省去回溯过程;
            int k = nex.find(' ');
            int x = k/3;
            int y = k%3;
            int x1 = x+dx[i];
            int y1 = y+dy[i];
            int k1 = x1*3 + y1;
            if(x1<0||y1<0||x1>=2||y1>=3)continue;//next越界continue;
            swap(nex[k],nex[k1]);
            if(mp.count(nex))continue;//通过map容器的count函数判断next是否为新//不为新，结束
            else{ //为新，queue入队next,同时map入队[next]，它的值是map[now]+1 
                mp[nex] = mp[no]+1;
                q.push(nex);
            }
            if(nex.find('A') == bpo&&nex.find('B')==apo)return mp[nex];
            //  判断是否找到答案。如果找到答案，返回map[next]
        }// for循环下一次 
    }
}
int main(){
    string a;
    getline(cin,fir);
    getline(cin,a);
    fir += a;
    apo = fir.find('A');
    bpo = fir.find('B'); 
    int ans = bfs();
    cout<<ans;
}