【搜索】B083_LQ_青蛙跳杯子（bfs+枚举所有位置）

83 阅读 0 评论 55 点赞

我是靠谱客的博主儒雅帆布鞋，最近开发中收集的这篇文章主要介绍【搜索】B083_LQ_青蛙跳杯子（bfs+枚举所有位置），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

X星球的流行宠物是青蛙，一般有两种颜色：白色和黑色。
X星球的居民喜欢把它们放在一排茶杯里，这样可以观察它们跳来跳去。
如下图，有一排杯子，左边的一个是空着的，右边的杯子，每个里边有一只青蛙。

*WWWBBB

其中，W字母表示白色青蛙，B表示黑色青蛙，*表示空杯子。
X星的青蛙很有些癖好，它们只做3个动作之一

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

对于上图的局面，只要1步，就可跳成该局面：WWW*BBB
本题的任务就是已知初始局面，询问至少需要几步，才能跳成另一个目标局面。

输入
输入存在多组测试数据，对于每组测试数据：
输入为2行，2个串，表示初始局面和目标局面。输入的串的长度不超过15
输出
对于每组测试数据：输出要求为一个整数，表示至少需要多少步的青蛙跳

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

方法一：bfs

由于不知道从哪个位置开始交换，所以只能枚举所有可跳的位置

getline 服了…

#include<bits/stdc++.h>
using namespace std;
struct node{
    string s;
    int c;
};
const int d[6] = {-3, -2, -1, 1, 2, 3};
int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    string start, target;  cin>>start>>target;
    
    queue<node> q; q.push({start, 0});
    unordered_map<string, bool> bk; bk[start]=1;
    
    int n=start.size();
    while (!q.empty()) {
        auto& t=q.front(); int c=t.c; string now=t.s;
        if (now==target) {
            return cout<<c, 0;
        }
        q.pop();
        for (int j=0; j<n; j++)
        for (int k=0; k<6; k++) {
            int nj=j+d[k];
            if (nj>=0 && nj<n && now[nj]=='*') {
                string nx=now;
                swap(nx[j], nx[nj]);
                if (!bk[nx]) {
                    q.push({nx, c+1});
                    bk[nx]=1;
                }
            }
        }
    }
    return 0;
}