如何用BFS算法实现6x6网格迷宫最短路径（C#）

我来帮你搞定这个迷宫最短路径的问题！你已经完成了迷宫读取的基础工作，现在只需要补上BFS算法的核心实现，以及路径回溯的逻辑就能得到你想要的结果。先理清楚几个关键问题，再一步步修改代码：

首先修正初始读取逻辑 #

你当前的代码把所有., B, E都直接转成O了，这样会丢失起点和终点的位置，也无法区分“可行路径”和“已标记路径”。正确的做法是先保留原始迷宫结构，同时记录起点B和终点E的坐标：

int startI = -1, startJ = -1;
int endI = -1, endJ = -1;
char[,] Tablero = new char[6, 6];
string[] lines = File.ReadAllLines("maze.txt");

for (int i = 0; i < lines.Length; i++) {
    for (int j = 0; j < lines[i].Length; j++) {
        Tablero[i, j] = lines[i][j];
        // 记录起点和终点坐标
        if (Tablero[i, j] == 'B') {
            startI = i;
            startJ = j;
        } else if (Tablero[i, j] == 'E') {
            endI = i;
            endJ = j;
        }
        Console.Write(Tablero[i, j]);
    }
    Console.WriteLine();
}

实现BFS算法找最短路径 #

BFS的核心是逐层遍历，第一次到达终点的路径就是最短路径。我们需要：

• 一个队列来存储待遍历的坐标
• 一个前驱数组来记录每个位置的上一个位置（用于回溯路径）
• 一个访问数组来避免重复遍历

// 定义上下左右四个移动方向
int[][] dirs = new int[][] {
    new int[] {-1, 0}, // 上
    new int[] {1, 0},  // 下
    new int[] {0, -1}, // 左
    new int[] {0, 1}   // 右
};

// 前驱数组：记录每个位置的来源坐标，用于回溯路径
(int?, int?)[,] prev = new (int?, int?)[6, 6];
// 访问数组：标记是否已经遍历过该位置
bool[,] visited = new bool[6, 6];
Queue<Tuple<int, int>> queue = new Queue<Tuple<int, int>>();

// 从起点开始BFS
queue.Enqueue(Tuple.Create(startI, startJ));
visited[startI, startJ] = true;
bool foundEnd = false;

while (queue.Count > 0 && !foundEnd) {
    var current = queue.Dequeue();
    int currI = current.Item1;
    int currJ = current.Item2;

    // 检查是否到达终点
    if (currI == endI && currJ == endJ) {
        foundEnd = true;
        break;
    }

    // 遍历四个方向
    foreach (var dir in dirs) {
        int newI = currI + dir[0];
        int newJ = currJ + dir[1];

        // 检查边界：是否在6x6网格内
        if (newI >= 0 && newI < 6 && newJ >= 0 && newJ < 6) {
            // 检查是否是可行路径（不是墙壁X，且未被访问过）
            if ((Tablero[newI, newJ] == '.' || Tablero[newI, newJ] == 'E') && !visited[newI, newJ]) {
                visited[newI, newJ] = true;
                // 记录当前位置的前驱
                prev[newI, newJ] = (currI, currJ);
                queue.Enqueue(Tuple.Create(newI, newJ));
            }
        }
    }
}

回溯路径并标记为O #

找到终点后，我们从终点往起点回溯，把路径上的所有位置（包括起点B和终点E）替换成O：

if (foundEnd) {
    // 从终点开始回溯
    int currI = endI;
    int currJ = endJ;

    while (currI != -1 && currJ != -1) {
        Tablero[currI, currJ] = 'O';
        // 获取前驱坐标
        var prevPos = prev[currI, currJ];
        // 更新当前坐标为前驱坐标，起点的前驱是(null,null)，所以退出循环
        currI = prevPos.Item1 ?? -1;
        currJ = prevPos.Item2 ?? -1;
    }

    // 输出标记后的迷宫
    Console.WriteLine("\n最短路径标记结果：");
    for (int i = 0; i < 6; i++) {
        for (int j = 0; j < 6; j++) {
            Console.Write(Tablero[i, j]);
        }
        Console.WriteLine();
    }
} else {
    Console.WriteLine("\n没有找到从起点到终点的路径！");
}

完整代码整合 #

把以上部分整合到你的Program类中，完整代码如下：

using System;
using System.Collections.Generic;
using System.IO;

class Program {
    static void Main(string[] args) {
        int startI = -1, startJ = -1;
        int endI = -1, endJ = -1;
        char[,] Tablero = new char[6, 6];
        string[] lines = File.ReadAllLines("maze.txt");

        // 读取迷宫并记录起点终点
        for (int i = 0; i < lines.Length; i++) {
            for (int j = 0; j < lines[i].Length; j++) {
                Tablero[i, j] = lines[i][j];
                if (Tablero[i, j] == 'B') {
                    startI = i;
                    startJ = j;
                } else if (Tablero[i, j] == 'E') {
                    endI = i;
                    endJ = j;
                }
                Console.Write(Tablero[i, j]);
            }
            Console.WriteLine();
        }

        // BFS找最短路径
        int[][] dirs = new int[][] {
            new int[] {-1, 0},
            new int[] {1, 0},
            new int[] {0, -1},
            new int[] {0, 1}
        };

        (int?, int?)[,] prev = new (int?, int?)[6, 6];
        bool[,] visited = new bool[6, 6];
        Queue<Tuple<int, int>> queue = new Queue<Tuple<int, int>>();

        queue.Enqueue(Tuple.Create(startI, startJ));
        visited[startI, startJ] = true;
        bool foundEnd = false;

        while (queue.Count > 0 && !foundEnd) {
            var current = queue.Dequeue();
            int currI = current.Item1;
            int currJ = current.Item2;

            if (currI == endI && currJ == endJ) {
                foundEnd = true;
                break;
            }

            foreach (var dir in dirs) {
                int newI = currI + dir[0];
                int newJ = currJ + dir[1];

                if (newI >= 0 && newI < 6 && newJ >= 0 && newJ < 6) {
                    if ((Tablero[newI, newJ] == '.' || Tablero[newI, newJ] == 'E') && !visited[newI, newJ]) {
                        visited[newI, newJ] = true;
                        prev[newI, newJ] = (currI, currJ);
                        queue.Enqueue(Tuple.Create(newI, newJ));
                    }
                }
            }
        }

        // 回溯标记路径
        if (foundEnd) {
            int currI = endI;
            int currJ = endJ;

            while (currI != -1 && currJ != -1) {
                Tablero[currI, currJ] = 'O';
                var prevPos = prev[currI, currJ];
                currI = prevPos.Item1 ?? -1;
                currJ = prevPos.Item2 ?? -1;
            }

            Console.WriteLine("\n最短路径标记结果：");
            for (int i = 0; i < 6; i++) {
                for (int j = 0; j < 6; j++) {
                    Console.Write(Tablero[i, j]);
                }
                Console.WriteLine();
            }
        } else {
            Console.WriteLine("\n没有找到从起点到终点的路径！");
        }

        Console.ReadLine();
    }
}

测试结果 #

运行这段代码后，针对你提供的迷宫：

Bxxxxx
.....x
x.xx.x
x....x
x.xxxx
x....E

会输出你期望的结果：

Oxxxxx
OO...x
xOxx.x
xO...x
xOxxxx
xOOOOO

内容的提问来源于stack exchange，提问作者Sahak Wei