2017蓝桥杯省赛：青蛙跳杯子（BFS求最短路径长度）

川长思鸟来 2022-11-17 14:55 209阅读 0赞

【题目描述】  
  X星球的流行宠物是青蛙，一般有两种颜色：白色和黑色。

X星球的居民喜欢把它们放在一排茶杯里，这样可以观察它们跳来跳去。

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

\*WWWBBB  
  其中，W字母表示白色青蛙，B表示黑色青蛙，∗表示空杯子。

XX星的青蛙很有些癖好，它们只做3个动作之一：

1.  跳到相邻的空杯子里。
2.  隔着1只其它的青蛙（随便什么颜色）跳到空杯子里。
3.  隔着2只其它的青蛙（随便什么颜色）跳到空杯子里。

对于上图的局面，只要1步，就可跳成下图局面：

WWW\*BBB

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

【输入描述】  
  输入为2行，2个串，表示初始局面和目标局面。我们约定，输入的串的长度不超过15。

【输出描述】  
  输出要求为一个整数，表示至少需要多少步的青蛙跳。

【思路分析】  
  此题跟八数码问题类似。由于要求最短路径，这里我们考虑使用BFS：首先将初始的字符串入队列，在队列不为空的情况下：

1.  取队首字符串，若为目的字符串，则结束循环
2.  队首出队列
3.  对队首字符串分别考虑六种情况，即上述所描述的三种情况（分左右），将每一个字符串产生的下一状态（<=6种）入队列

【AC代码】

#include<bits/stdc++.h>
    using namespace std;
    
    string bg, ed;
    queue<pair<string, int>> que;
    int res;
    
    int main() { 
        cin >> bg;
        cin >> ed;
        pair<string, int> s;
        s.first = bg;
        s.second = 0;
        que.push(s);
        while(!que.empty()) { 
            pair<string, int> fr = que.front();
            string str = fr.first;
            int step = fr.second;
            string temp = str;
            if(str == ed) { 
                res = step;
                break;
            }
            que.pop();
            int index = str.find("*");
            //一共6种情况
            //1.左边相邻
            if(index > 0) { 
                temp = str;
                temp[index] = temp[index - 1];
                temp[index - 1] = '*';
                pair<string, int> p(temp, step + 1);
                que.push(p);
            }
            //2.左边隔一个
            if(index > 1) { 
                temp = str;
                temp[index] = temp[index - 2];
                temp[index - 2] = '*';
                pair<string, int> p(temp, step + 1);
                que.push(p);
            }
            //3.左边隔两个
            if(index > 2) { 
                temp = str;
                temp[index] = temp[index - 3];
                temp[index - 3] = '*';
                pair<string, int> p(temp, step + 1);
                que.push(p);
            }
            //4.右边相邻
            if(index < str.size() - 1) { 
                temp = str;
                temp[index] = temp[index + 1];
                temp[index + 1] = '*';
                pair<string, int> p(temp, step + 1);
                que.push(p);
            }
            //5.右边隔一个
            if(index < str.size() - 2) { 
                temp = str;
                temp[index] = temp[index + 2];
                temp[index + 2] = '*';
                pair<string, int> p(temp, step + 1);
                que.push(p);
            }
            //6.右边隔两个
            if(index < str.size() - 3) { 
                temp = str;
                temp[index] = temp[index + 3];
                temp[index + 3] = '*';
                pair<string, int> p(temp, step + 1);
                que.push(p);
            }
        }
        cout << res;
        return 0;
    }