题目链接
https://www.nowcoder.com/practice/80fe9a87ed034b70b23b029c5bab6d21
题目描述
在一个 的棋盘上，有若干个白马（用
1 表示）、黑马（用 0 表示）以及一个空格（用 * 表示）。马的移动遵循中国象棋的 “日” 字规则（无 “蹩马腿” 限制），即可以移动到8个可能的方向。给定一个初始棋盘布局，要求计算出最少需要多少步才能移动到如下所示的目标状态。
目标状态：
11111
01111
00*11
00001
00000
如果能在 15 步以内（含 15 步）到达，则输出最少步数；否则输出 -1。
解题思路
这是一个典型的状态搜索问题，我们需要在巨大的状态空间中寻找从初始状态到目标状态的最短路径。
-
状态表示： 一个
的棋盘状态可以通过将其 “压平” 成一个长度为 25 的字符串来唯一表示。例如，空格在第
行第
列（0-based），那么它在字符串中的索引就是
。
-
搜索算法选择： 直接从初始状态进行广度优先搜索（BFS）理论上可行，但搜索空间非常大。在最坏情况下，搜索深度为 15，每个状态最多有 8 个后续状态（分支因子为 8），总状态数可能接近
，会导致超时。
由于我们同时知道起点（初始状态）和终点（目标状态），因此双向广度优先搜索（Bi-directional BFS） 是一个更高效的选择。其核心思想是：
- 同时从初始状态和目标状态开始进行两个 BFS。一个称为前向搜索（Forward Search），另一个称为后向搜索（Backward Search）。
- 我们使用两个队列和两个哈希表（或 map）来分别记录两个方向的搜索队列和已访问状态及其距离。
- 搜索过程是交替进行的，每次扩展当前规模较小的一个搜索队列，以保持两个搜索前沿的均衡。
- 当一个方向的搜索生成了一个新状态，而这个状态已经被另一个方向的搜索访问过时，我们就找到了一个“相遇点”。此时，两条路径被连接起来，我们找到了从起点到终点的路径。由于 BFS 的性质，第一次相遇时找到的路径就是最短路径。
-
复杂度与剪枝： 双向 BFS 的时间复杂度大约为
，其中
是分支因子，
是最短路径长度。对于本题，
，复杂度约为
级别，远小于单向 BFS 的
，在可接受范围内。
题目要求步数不超过 15。这为我们提供了一个强力的剪枝条件。在双向 BFS 中，总步数是前向搜索步数与后向搜索步数之和。如果前向搜索走了
步，后向搜索走了
步，那么总步数是
。为了使总步数不超过 15，我们可以限制单向搜索的深度。例如，我们可以规定任何一个方向的搜索深度都不扩展超过 7 的节点（即最远只生成距离为 8 的节点）。这样，如果相遇，最大步数为
，正好符合题意。如果在此深度限制下未能相遇，则说明不存在 15 步以内的解。
代码
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
// 马走日的8个方向
int dx[8] = {-2, -2, -1, -1, 1, 1, 2, 2};
int dy[8] = {-1, 1, -2, 2, -2, 2, -1, 1};
string target_state = "111110111100*110000100000";
int bfs(const string& start_state) {
if (start_state == target_state) {
return 0;
}
queue<string> q_f, q_b;
map<string, int> dist_f, dist_b;
q_f.push(start_state);
dist_f[start_state] = 0;
q_b.push(target_state);
dist_b[target_state] = 0;
while (!q_f.empty() && !q_b.empty()) {
// 优先扩展较小的队列，以平衡搜索
if (q_f.size() <= q_b.size()) {
int len = q_f.size();
for (int i = 0; i < len; ++i) {
string current_state = q_f.front();
q_f.pop();
int d = dist_f[current_state];
if (d >= 8) continue; // 剪枝
size_t pos = current_state.find('*');
int x = pos % 5;
int y = pos / 5;
for (int j = 0; j < 8; ++j) {
int nx = x + dx[j];
int ny = y + dy[j];
if (nx >= 0 && nx < 5 && ny >= 0 && ny < 5) {
string next_state = current_state;
swap(next_state[pos], next_state[ny * 5 + nx]);
if (dist_f.find(next_state) == dist_f.end()) {
dist_f[next_state] = d + 1;
if (dist_b.count(next_state)) {
return d + 1 + dist_b[next_state];
}
q_f.push(next_state);
}
}
}
}
} else {
int len = q_b.size();
for (int i = 0; i < len; ++i) {
string current_state = q_b.front();
q_b.pop();
int d = dist_b[current_state];
if (d >= 8) continue; // 剪枝
size_t pos = current_state.find('*');
int x = pos % 5;
int y = pos / 5;
for (int j = 0; j < 8; ++j) {
int nx = x + dx[j];
int ny = y + dy[j];
if (nx >= 0 && nx < 5 && ny >= 0 && ny < 5) {
string next_state = current_state;
swap(next_state[pos], next_state[ny * 5 + nx]);
if (dist_b.find(next_state) == dist_b.end()) {
dist_b[next_state] = d + 1;
if (dist_f.count(next_state)) {
return d + 1 + dist_f[next_state];
}
q_b.push(next_state);
}
}
}
}
}
}
return -1;
}
int main() {
int t;
cin >> t;
while (t--) {
string start_state = "";
for (int i = 0; i < 5; ++i) {
string row;
cin >> row;
start_state += row;
}
int result = bfs(start_state);
if (result > 15) {
cout << -1 << "\n";
} else {
cout << result << "\n";
}
}
return 0;
}
import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;
import java.util.Map;
import java.util.HashMap;
public class Main {
private static final int[] dx = {-2, -2, -1, -1, 1, 1, 2, 2};
private static final int[] dy = {-1, 1, -2, 2, -2, 2, -1, 1};
private static final String targetState = "111110111100*110000100000";
private static int bfs(String startState) {
if (startState.equals(targetState)) {
return 0;
}
Queue<String> qF = new LinkedList<>();
Queue<String> qB = new LinkedList<>();
Map<String, Integer> distF = new HashMap<>();
Map<String, Integer> distB = new HashMap<>();
qF.add(startState);
distF.put(startState, 0);
qB.add(targetState);
distB.put(targetState, 0);
while (!qF.isEmpty() && !qB.isEmpty()) {
if (qF.size() <= qB.size()) {
int len = qF.size();
for (int i = 0; i < len; i++) {
String currentState = qF.poll();
int d = distF.get(currentState);
if (d >= 8) continue;
int pos = currentState.indexOf('*');
int x = pos % 5;
int y = pos / 5;
for (int j = 0; j < 8; j++) {
int nx = x + dx[j];
int ny = y + dy[j];
if (nx >= 0 && nx < 5 && ny >= 0 && ny < 5) {
char[] chars = currentState.toCharArray();
char temp = chars[pos];
chars[pos] = chars[ny * 5 + nx];
chars[ny * 5 + nx] = temp;
String nextState = new String(chars);
if (!distF.containsKey(nextState)) {
distF.put(nextState, d + 1);
if (distB.containsKey(nextState)) {
return d + 1 + distB.get(nextState);
}
qF.add(nextState);
}
}
}
}
} else {
int len = qB.size();
for (int i = 0; i < len; i++) {
String currentState = qB.poll();
int d = distB.get(currentState);
if (d >= 8) continue;
int pos = currentState.indexOf('*');
int x = pos % 5;
int y = pos / 5;
for (int j = 0; j < 8; j++) {
int nx = x + dx[j];
int ny = y + dy[j];
if (nx >= 0 && nx < 5 && ny >= 0 && ny < 5) {
char[] chars = currentState.toCharArray();
char temp = chars[pos];
chars[pos] = chars[ny * 5 + nx];
chars[ny * 5 + nx] = temp;
String nextState = new String(chars);
if (!distB.containsKey(nextState)) {
distB.put(nextState, d + 1);
if (distF.containsKey(nextState)) {
return d + 1 + distF.get(nextState);
}
qB.add(nextState);
}
}
}
}
}
}
return -1;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while (t-- > 0) {
StringBuilder startStateSb = new StringBuilder();
for (int i = 0; i < 5; i++) {
startStateSb.append(sc.next());
}
String startState = startStateSb.toString();
int result = bfs(startState);
if (result > 15) {
System.out.println(-1);
} else {
System.out.println(result);
}
}
}
}
from collections import deque
def solve():
# 马走日的8个方向
dx = [-2, -2, -1, -1, 1, 1, 2, 2]
dy = [-1, 1, -2, 2, -2, 2, -1, 1]
target_state = "111110111100*110000100000"
def bfs(start_state):
if start_state == target_state:
return 0
q_f = deque([start_state])
dist_f = {start_state: 0}
q_b = deque([target_state])
dist_b = {target_state: 0}
while q_f and q_b:
# 优先扩展前向队列
if len(q_f) <= len(q_b):
len_q = len(q_f)
for _ in range(len_q):
current_state = q_f.popleft()
d = dist_f[current_state]
if d >= 8: # 剪枝
continue
pos = current_state.find('*')
x, y = pos % 5, pos // 5
for i in range(8):
nx, ny = x + dx[i], y + dy[i]
if 0 <= nx < 5 and 0 <= ny < 5:
n_pos = ny * 5 + nx
s_list = list(current_state)
s_list[pos], s_list[n_pos] = s_list[n_pos], s_list[pos]
next_state = "".join(s_list)
if next_state not in dist_f:
dist_f[next_state] = d + 1
if next_state in dist_b:
return d + 1 + dist_b[next_state]
q_f.append(next_state)
else:
# 扩展后向队列
len_q = len(q_b)
for _ in range(len_q):
current_state = q_b.popleft()
d = dist_b[current_state]
if d >= 8: # 剪枝
continue
pos = current_state.find('*')
x, y = pos % 5, pos // 5
for i in range(8):
nx, ny = x + dx[i], y + dy[i]
if 0 <= nx < 5 and 0 <= ny < 5:
n_pos = ny * 5 + nx
s_list = list(current_state)
s_list[pos], s_list[n_pos] = s_list[n_pos], s_list[pos]
next_state = "".join(s_list)
if next_state not in dist_b:
dist_b[next_state] = d + 1
if next_state in dist_f:
return d + 1 + dist_f[next_state]
q_b.append(next_state)
return -1
# 主程序逻辑
t = int(input())
for _ in range(t):
start_state = ""
for _ in range(5):
start_state += input()
result = bfs(start_state)
if result > 15:
print(-1)
else:
print(result)
solve()
算法及复杂度
- 算法：双向广度优先搜索 (Bi-directional BFS)
- 时间复杂度：
级别的计算量，每个状态的操作是常数时间，可以通过。
- 空间复杂度：
map和queue，与时间复杂度同阶。
京公网安备 11010502036488号