题目
星球的流行宠物是青蛙，一般有两种颜色：白色和黑色。
星球的居民喜欢把它们放在一排茶杯里，这样可以观察它们跳来跳去。
如下图，有一排杯子，左边的一个是空着的，右边的杯子，每个里边有一只青蛙。
*WWWBBB
其中，W 字母表示白色青蛙，B 字母表示黑色青蛙，* 表示空杯子。
星的青蛙很有些癖好，它们只做 个动作之一：
- 跳到相邻的空杯子里。
- 隔着 只其它的青蛙（随便什么颜色）跳到空杯子里。
- 隔着 只其它的青蛙（随便什么颜色）跳到空杯子里。
对于上图的局面，只要 步，就可跳成下图局面：
WWW*BBB
本题的任务就是已知初始局面，询问至少需要几步，才能跳成另一个目标局面。
输入格式
输入为 行， 个串，表示初始局面和目标局面。
输出格式
输出要求为一个整数，表示至少需要多少步的青蛙跳。
数据范围
输入的串的长度不超过 。
数据保证只有一个空杯子。
输入样例1：
*WWBB
WWBB*
输出样例1：
2
输入样例2：
WWW*BBB
BBB*WWW
输出样例2：
10
解题
方法一：BFS
思路
广度优先搜索应用题，把表示杯子情况的字符串作为状态(state)，每次先从队列中取出状态，与目标局面(target)进行对比，如果已经达到目标就直接从哈希表中取出步数(step)并返回(因为 BFS 是一层一层进行查找的，所以第一次找到的步数一定是最短步数)，否则找到空杯子的位置(pos)( 字符串中 '*' 的位置)，相对于该空杯 -3、-2、-1、1、2、3 的位置(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;
}
}
评论区