题解

问题分析

在一个 m * m 的网格中，小明需要踢球，球经过障碍物和边界会停下。目标是计算小明将球踢入球门的最少踢球次数，若无法将球踢入球门则返回 -1。为了记录状态，我们需要四个变量来存储小明和球的位置。

解题思路:0-1 BFS

1. 多维度状态记录：

   • 使用 dist[x][y][fx][fy] 数组记录小明和球在不同位置的最小踢球次数。这里 x, y 表示小明的位置，fx, fy 表示球的位置。
   • 初始值 -1 表示该状态未被访问。

2. 初始化位置：

   • 通过遍历网格，找到小明、球和球门的初始坐标，分别记为 (sx, sy)、(fx, fy)、(ex, ey)。

3. 0-1 BFS 队列初始化：

   • 使用双端队列 deque 实现 0-1 BFS。
   • 初始时，将小明和球的位置 (sx, sy, fx, fy) 入队，并将 dist[sx][sy][fx][fy] 初始化为 0，表示从起始状态出发，最少踢球次数为 0。

4. 状态转移过程：

   • 进行 BFS 扩展时，遍历小明的四个移动方向 (dx, dy)。
   • 小明移动：
     • 对于每一个方向，计算小明移动后的新位置 (nx, ny)，跳过超出边界或遇到障碍物的位置。
     • 如果小明移动后的位置与球的当前位置相同，表示要踢球。
       • 计算球在踢动后的位置 (nnx, nny)，并检查新位置的有效性（不超出边界且不是障碍物）。
       • 如果 dist[nx][ny][nnx][nny] == -1，则更新 dist 并将新状态加入队列尾部（踢球算作一步，因此边权为 1）。
       • 若球的位置达到球门，则更新 ans 为当前的踢球次数，并返回。
     • 如果小明移动后没有踢球（nx, ny 位置与球不同），则直接将新状态入队列头部（边权为 0）。

5. 返回结果：

   • 若找到最短路径，则返回 ans。若搜索结束未找到可行路径，则返回 -1。

代码解析

from collections import deque

m = int(input())
arr = [list(map(str, input().split())) for _ in range(m)]

# 初始化小明、球和球门的位置
sx, sy, ex, ey, fx, fy = 0, 0, 0, 0, 0, 0
for i in range(m):
    for j in range(m):
        if arr[i][j] == 'B':
            fx, fy = i, j
        if arr[i][j] == 'G':
            ex, ey = i, j
        if arr[i][j] == 'X':
            sx, sy = i, j

# 移动方向
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

# 4维距离数组，记录状态
dist = [[[[-1] * m for _ in range(m)] for _ in range(m)] for _ in range(m)]

def bfs():
    global sx, sy, ex, ey, fx, fy
    q = deque()
    q.append((sx, sy, fx, fy))
    dist[sx][sy][fx][fy] = 0
    ans = -1
    
    while q:
        x, y, fx, fy = q.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if nx < 0 or nx >= m or ny < 0 or ny >= m or arr[nx][ny] == '1':
                continue
            # 检查是否需要踢球
            if nx == fx and ny == fy:
                nnx, nny = fx + dx[i], fy + dy[i]
                if nnx < 0 or nnx >= m or nny < 0 or nny >= m or arr[nnx][nny] == '1':
                    continue
                if dist[nx][ny][nnx][nny] == -1:
                    dist[nx][ny][nnx][nny] = dist[x][y][fx][fy] + 1
                    q.append((nx, ny, nnx, nny))
                    if nnx == ex and nny == ey:
                        if ans == -1 or ans > dist[nx][ny][nnx][nny]:
                            ans = dist[nx][ny][nnx][nny]
                            return ans
            else:
                if dist[nx][ny][fx][fy] == -1:
                    dist[nx][ny][fx][fy] = dist[x][y][fx][fy]
                    q.appendleft((nx, ny, fx, fy))

    return -1

print(bfs())

cpp

#include <iostream>
#include <deque>
#include <vector>
#include <cstring>
using namespace std;

int m; // 地图的大小
vector<vector<string>> arr; // 存储地图
int sx, sy, ex, ey, fx, fy; // 小明起始位置(sx, sy)，球门位置(ex, ey)，球位置(fx, fy)
int dx[] = {0, 0, 1, -1}; // 四个方向的横坐标变化量
int dy[] = {1, -1, 0, 0}; // 四个方向的纵坐标变化量
int dist[50][50][50][50]; // 记录每个状态的最短距离

// BFS函数
int bfs() {
    deque<tuple<int, int, int, int>> q; // 队列存储当前状态
    q.push_back({sx, sy, fx, fy}); // 将起始位置入队
    dist[sx][sy][fx][fy] = 0; // 初始化距离
    int ans = -1; // 最终答案，若无法到达则为-1

    // BFS循环
    while (!q.empty()) {
        auto [x, y, fx, fy] = q.front(); // 获取队首的状态
        q.pop_front(); // 队首出队

        for (int i = 0; i < 4; ++i) { // 遍历四个方向
            int nx = x + dx[i], ny = y + dy[i]; // 计算新的位置
            if (nx < 0 || nx >= m || ny < 0 || ny >= m || arr[nx][ny] == "1") continue; // 超出边界或遇到障碍物

            // 如果新位置是球的位置，则尝试踢球
            if (nx == fx && ny == fy) {
                int nnx = fx + dx[i], nny = fy + dy[i]; // 计算踢球后新的球位置
                if (nnx < 0 || nnx >= m || nny < 0 || nny >= m || arr[nnx][nny] == "1") continue; // 如果踢球位置超出边界或遇到障碍
                if (dist[nx][ny][nnx][nny] == -1) { // 如果该状态未被访问
                    dist[nx][ny][nnx][nny] = dist[x][y][fx][fy] + 1; // 更新距离
                    q.push_back({nx, ny, nnx, nny}); // 将新状态入队
                    if (nnx == ex && nny == ey) { // 如果球已经进了球门
                        if (ans == -1 || ans > dist[nx][ny][nnx][nny]) {
                            ans = dist[nx][ny][nnx][nny]; // 更新最短路径
                            return ans; // 直接返回答案
                        }
                    }
                }
            } else { // 如果没有踢球，直接移动
                if (dist[nx][ny][fx][fy] == -1) { // 如果该状态未被访问
                    dist[nx][ny][fx][fy] = dist[x][y][fx][fy]; // 保持距离不变
                    q.push_front({nx, ny, fx, fy}); // 将新的移动状态加入队列
                }
            }
        }
    }
    return -1; // 如果找不到解，返回-1
}

int main() {
    cin >> m; // 输入地图大小
    arr.resize(m, vector<string>(m)); // 初始化地图
    // 读取地图数据，并找到起始位置、小明位置、球位置和球门位置
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> arr[i][j];
            if (arr[i][j] == "B") {
                fx = i, fy = j; // 球的位置
            }
            if (arr[i][j] == "G") {
                ex = i, ey = j; // 球门的位置
            }
            if (arr[i][j] == "X") {
                sx = i, sy = j; // 小明的位置
            }
        }
    }
    
    memset(dist, -1, sizeof(dist)); // 初始化dist数组为-1
    cout << bfs() << endl; // 执行BFS并输出结果

    return 0;
}

java

import java.util.*;

public class Main {
    static int m; // 地图的大小
    static String[][] arr; // 存储地图
    static int sx, sy, ex, ey, fx, fy; // 小明起始位置(sx, sy)，球门位置(ex, ey)，球位置(fx, fy)
    static int[] dx = {0, 0, 1, -1}; // 四个方向的横坐标变化量
    static int[] dy = {1, -1, 0, 0}; // 四个方向的纵坐标变化量
    static int[][][][] dist = new int[50][50][50][50]; // 记录每个状态的最短距离

    // BFS函数
    public static int bfs() {
        Deque<int[]> q = new ArrayDeque<>(); // 队列存储当前状态
        q.add(new int[]{sx, sy, fx, fy}); // 将起始位置入队
        dist[sx][sy][fx][fy] = 0; // 初始化距离
        int ans = -1; // 最终答案，若无法到达则为-1

        // BFS循环
        while (!q.isEmpty()) {
            int[] front = q.poll(); // 获取队首的状态
            int x = front[0], y = front[1], fx = front[2], fy = front[3];

            for (int i = 0; i < 4; i++) { // 遍历四个方向
                int nx = x + dx[i], ny = y + dy[i]; // 计算新的位置
                if (nx < 0 || nx >= m || ny < 0 || ny >= m || arr[nx][ny].equals("1")) continue; // 超出边界或遇到障碍物

                // 如果新位置是球的位置，则尝试踢球
                if (nx == fx && ny == fy) {
                    int nnx = fx + dx[i], nny = fy + dy[i]; // 计算踢球后新的球位置
                    if (nnx < 0 || nnx >= m || nny < 0 || nny >= m || arr[nnx][nny].equals("1")) continue; // 如果踢球位置超出边界或遇到障碍
                    if (dist[nx][ny][nnx][nny] == -1) { // 如果该状态未被访问
                        dist[nx][ny][nnx][nny] = dist[x][y][fx][fy] + 1; // 更新距离
                        q.add(new int[]{nx, ny, nnx, nny}); // 将新状态入队
                        if (nnx == ex && nny == ey) { // 如果球已经进了球门
                            if (ans == -1 || ans > dist[nx][ny][nnx][nny]) {
                                ans = dist[nx][ny][nnx][nny]; // 更新最短路径
                                return ans; // 直接返回答案
                            }
                        }
                    }
                } else { // 如果没有踢球，直接移动
                    if (dist[nx][ny][fx][fy] == -1) { // 如果该状态未被访问
                        dist[nx][ny][fx][fy] = dist[x][y][fx][fy]; // 保持距离不变
                        q.addFirst(new int[]{nx, ny, fx, fy}); // 将新的移动状态加入队列
                    }
                }
            }
        }
        return -1; // 如果找不到解，返回-1
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        m = sc.nextInt(); // 输入地图大小
        arr = new String[m][m]; // 初始化地图
        // 读取地图数据，并找到起始位置、小明位置、球位置和球门位置
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < m; j++) {
                arr[i][j] = sc.next();
                if (arr[i][j].equals("B")) {
                    fx = i; fy = j; // 球的位置
                }
                if (arr[i][j].equals("G")) {
                    ex = i; ey = j; // 球门的位置
                }
                if (arr[i][j].equals("X")) {
                    sx = i; sy = j; // 小明的位置
                }
            }
        }

        // 初始化dist数组为-1
        for (int[][][] layer1 : dist) {
            for (int[][] layer2 : layer1) {
                for (int[] layer3 : layer2) {
                    Arrays.fill(layer3, -1);
                }
            }
        }

        System.out.println(bfs()); // 执行BFS并输出结果
    }
}

总结

这段代码利用 0-1 BFS，通过多维数组跟踪每一种状态下的最少踢球次数，并在每次移动和踢球时更新队列与状态。小明的移动不增加踢球次数，因此使用双端队列进行操作，而每次踢球则计为一次操作（边权为 1）。通过这种方法，代码实现了最短路径的查找。