题目描述

如下图，有一排杯子，左边的一个是空着的，右边的杯子，每个里边有一只青蛙。

WWWBBB 其中，W 字母表示白色青蛙，B 字母表示黑色青蛙， 表示空杯子。
跳到相邻的空杯子里。
隔着 1
只其它的青蛙（随便什么颜色）跳到空杯子里。
隔着 2
只其它的青蛙（随便什么颜色）跳到空杯子里。
对于上图的局面，只要 1
步，就可跳成下图局面：

WWW*BBB

本题的任务就是已知初始局面，询问至少需要几步，才能跳成另一个目标局面。

输入格式
输入为 2
行，2
个串，表示初始局面和目标局面。

输出格式
输出要求为一个整数，表示至少需要多少步的青蛙跳。

数据范围
输入的串的长度不超过 15
。
数据保证只有一个空杯子。

样例

输入样例1：
*WWBB
WWBB*
输出样例1：
2
输入样例2：
WWW*BBB
BBB*WWW
输出样例2：
10

算法1

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

blablabla

时间复杂度

参考文献

C++ 代码

#include<bits/stdc++.h>
using namespace std;
unordered_map<string,int> d;
queue<string> q;
const int dx[] = { -3, -2, -1, 1, 2, 3};
string st,ed;
void bfs(string st) {
    d[st] = 0;
    if(st == ed) return;
    q.push(st);
    while(q.size()) {
        auto s = q.front(); q.pop();
        int x = s.find('*');
        for(int i = 0; i <= 5; i++) {
           int nx = x + dx[i];
           if(nx < 0 || nx >= s.length()) continue;
           int dis = d[s];
           swap(s[x],s[nx]);
           if(!d.count(s)) {
               d[s] = dis + 1;
               q.push(s);
           }
           swap(s[x],s[nx]);
        }
    }
}

int main() {
    getline(cin,st);
    getline(cin,ed);

    bfs(st);

    cout << d[ed] << endl;


    return 0;
}
blablabla

算法2

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla