侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【BFS】青蛙跳杯子【蓝桥杯】

GabrielxD
2022-09-26 / 0 评论 / 0 点赞 / 64 阅读 / 1,422 字 / 正在检测是否收录...

题目

试题 历届真题 青蛙跳杯子【第八届】【省赛】【C组】

3163. 青蛙跳杯子


XX 星球的流行宠物是青蛙,一般有两种颜色:白色和黑色。

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

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

*WWWBBB

其中,W 字母表示白色青蛙,B 字母表示黑色青蛙,* 表示空杯子。

XX 星的青蛙很有些癖好,它们只做 33 个动作之一:

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

对于上图的局面,只要 11 步,就可跳成下图局面:

WWW*BBB

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

输入格式

输入为 22 行,22 个串,表示初始局面和目标局面。

输出格式

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

数据范围

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

输入样例1:

*WWBB
WWBB*

输出样例1:

2

输入样例2:

WWW*BBB
BBB*WWW

输出样例2:

10

解题

方法一:BFS

思路

广度优先搜索应用题,把表示杯子情况的字符串作为状态(state),每次先从队列中取出状态,与目标局面(target)进行对比,如果已经达到目标就直接从哈希表中取出步数(step)并返回(因为 BFS 是一层一层进行查找的,所以第一次找到的步数一定是最短步数),否则找到空杯子的位置(pos)( 字符串中 '*' 的位置),相对于该空杯 -3-2-1123 的位置(targetPos)如果有效(不越界、状态不重复)的话就可以与其进行交换,然后把步数加一并进入下一层深搜。

注意:交换位置进入下一层后需要再次交换还原位置,不然会对下一次的位置(targetPos)判断有影响。

代码

import java.util.*;
import java.io.*;

public class _B {
    static String origin, target;
    static Map<String, Integer> map = new HashMap<>();
    static Queue<String> que = new LinkedList<>();
    static int n;

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        origin = in.readLine();
        target = in.readLine();
        n = origin.length();
        que.offer(origin);
        System.out.println(bfs());
    }

    static int bfs() {
        while (!que.isEmpty()) {
            String state = que.poll();
            int step = map.getOrDefault(state, 0);
            if (state.equals(target)) return step;
            int pos = state.indexOf('*');
            for (int offset = -3; offset <= 3; ++offset) {
                if (offset == 0) continue;
                int targetPos = pos + offset;
                if (targetPos >= 0 && targetPos < n) {
                    state = swap(state, pos, targetPos);
                    if (!map.containsKey(state)) {
                        map.put(state, step + 1);
                        que.offer(state);
                    }
                    state = swap(state, pos, targetPos);
                }
            }
        }
        return -1;
    }

    static String swap(String str, int i, int j) {
        char[] chs = str.toCharArray();
        char tmp = chs[i];
        chs[i] = chs[j];
        chs[j] = tmp;
        return String.valueOf(chs);
    }
}
#include <iostream>
#include <queue>
#include <unordered_map>

using namespace std;

string origin, target;
int n;

int bfs() {
    queue<string> que;
    unordered_map<string, int> mp;
    que.push(origin);
    while (!que.empty()) {
        string state = que.front();
        que.pop();
        int step = mp[state];
        if (state == target) return step;
        int pos = state.find('*');
        for (int offset = -3; offset <= 3; ++offset) {
            if (offset == 0) continue;
            int target_pos = pos + offset;
            if (target_pos >= 0 && target_pos < n) {
                swap(state[pos], state[target_pos]);
                if (mp.find(state) == mp.end()) {
                    mp[state] += step + 1;
                    que.push(state);
                }
                swap(state[pos], state[target_pos]);
            }
        }
    }
    return -1;
}

int main() {
    getline(cin, origin);
    getline(cin, target);
    n = origin.size();
    printf("%d\n", bfs());
    return 0;
}

设计状态类(State)套BFS模板

import java.util.*;
import java.io.*;

public class _B_class {
    static class State {
        char[] cups;
        int step, emptyPos = -1;

        State(char[] cups, int step) {
            this.cups = cups;
            this.step = step;
            // 收入当前杯子状态后获取空杯子的位置
            for (int i = 0; i < cups.length; ++i) {
                if (cups[i] == '*') {
                    this.emptyPos = i;
                    break;
                }
            }
        }

        // 重写equals方法用于对比现有状态与目标状态 故只用对比cups字符数组即可
        @Override
        public boolean equals(Object obj) {
            if (!(obj instanceof State)) return false;
            State s = (State) obj;
            int n = this.cups.length;
            for (int i = 0; i < n; ++i) {
                if (this.cups[i] != s.cups[i]) return false;
            }
            return true;
        }

        // 重写hashCode方法用于存入集合 以便于后面快速确认状态的存在与否
        @Override
        public int hashCode() {
            return Arrays.hashCode(this.cups);
        }

        // 由当前状态引入新状态 也就是让pos位的青蛙跳到当前状态的空杯中
        // 然后增加步数 生成新状态
        State newFrom(int pos) {
            char[] newCups = Arrays.copyOf(cups, cups.length);
            newCups[emptyPos] = cups[pos];
            newCups[pos] = cups[emptyPos];
            return new State(newCups, step + 1);
        }
    }

    static State origin, target;
    static Queue<State> que = new LinkedList<>();
    static Set<State> set = new HashSet<>();
    static int n;
    
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        // 输入状态 初始状态的步数皆为 0
        origin = new State(in.readLine().toCharArray(), 0);
        target = new State(in.readLine().toCharArray(), 0);
        n = target.cups.length;
        System.out.println(bfs());
    }

    static int bfs() {
        que.offer(origin);
        while (!que.isEmpty()) {
            State state = que.poll();
            // base case 当前状态和达到目标则直接返回步数即是最短步数
            if (state.equals(target)) return state.step;
            // 枚举可能的跳跃位置
            for (int offset = -3; offset <= 3; ++offset) {
                if (offset == 0) continue;
                // 计算跳过来的位置
                int targetPos = state.emptyPos + offset;
                // 筛选合法的跳跃位置
                if (targetPos >= 0 && targetPos < n) {
                    // 生成新状态
                    State newState = state.newFrom(targetPos);
                    // 若新生成的状态没重复就把它加入队列与集合
                    if (!set.contains(newState)) {
                        set.add(newState);
                        que.add(newState);
                    }
                }
            }
        }
        return -1;
    }
}
0

评论区