使用递归 DFS 打印迷宫中的所有可能路径

Question

这是任务：给你一个迷宫，它由N x N个方格组成，每个方格都可以通过，也可以不通过。可通过的单元格由 "a" 和 "z" 之间的小写拉丁字母和不可通过的 - '#' 组成。在其中一个广场上是杰克。用“*”标记。

两个方格是相邻的，如果它们有共同的墙。杰克一步可以从一个可通行的方格到达其相邻的可通行方格。当杰克经过可通行的方格时，他记下每个方格的字母。在每个出口，他都会得到一个词。编写一个程序，从给定的迷宫中打印出杰克从所有可能的出口中得到的单词。输入数据是从名为 Labyrinth.in 的文本文件中读取的。在文件的第一行有数字 N (2 < N < 10)。在接下来的 N 行中，每一行都有 N 个字符，每个字符要么是介于 "a" 和 "z" 之间的拉丁字母，要么是“#”（不可逾越的墙）或“*”（Jack）。输出必须打印在文件 Labyrinth.out.

中

输入：

6
a##km#
z#ada#
a*m###
#d####
rifid#
#d#d#t

到目前为止我已经做到了：

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

public class Maze
{
    private const string InputFileName = "Labyrinth.in";
    private const string OutputFileName = "Labyrinth.out";
    StringBuilder path = new StringBuilder();

    public class Cell
    {
        public int Row { get; set; }
        public int Column { get; set; }

        public Cell(int row, int column)
        {
            this.Row = row;
            this.Column = column;
        }
    }

    private char[,] maze;
    private int size;
    private Cell startCell = null;

    public void ReadFromFile(string fileName)
    {
        using (StreamReader reader = new StreamReader(fileName))
        {
            // Read maze size and create maze
            this.size = int.Parse(reader.ReadLine());
            this.maze = new char[this.size, this.size];

            // Read the maze cells from the file
            for (int row = 0; row < this.size; row++)
            {
                string line = reader.ReadLine();
                for (int col = 0; col < this.size; col++)
                {
                    this.maze[row, col] = line[col];
                    if (line[col] == '*')
                    {
                        this.startCell = new Cell(row, col);
                    }
                }
            }
        }
    }

    public void FindAllPathsAndPrintThem()
    {
        if (this.startCell == null)
        {
            // Start cell is missing -> no path
            SaveResult(OutputFileName, "");
            return;
        }

        VisitCell(this.startCell.Row,
            this.startCell.Column, path);

        if (path.Length == 0)
        {
            // We didn't reach any cell at the maze border -> no path
            SaveResult(OutputFileName, "");
            return;
        }
    }

    private void VisitCell(int row, int column, StringBuilder path)
    {
        if (row < 0 || row > maze.GetLength(0) - 1 ||
            column < 0 || column > maze.GetLength(1) - 1)
        {
            SaveResult(OutputFileName, path.ToString());
            return;
        }

        if (this.maze[row, column] != 'x' && this.maze[row, column] != '#')
        {
            // The cell is free --> visit it
            if (this.maze[row, column] != '*')
            {
                path.Append(this.maze[row, column]);
                this.maze[row, column] = 'x';
            }
            VisitCell(row, column + 1, path);
            VisitCell(row, column - 1, path);
            VisitCell(row + 1, column, path);
            VisitCell(row - 1, column, path);
        }
    }

    public void SaveResult(string fileName, string result)
    {
        using (StreamWriter writer = new StreamWriter(fileName))
        {
            writer.WriteLine(result);
        }
    }

    static void Main()
    {
        Maze maze = new Maze();
        maze.ReadFromFile(InputFileName);
        maze.FindAllPathsAndPrintThem();
    }
}

抱歉，问题很长。需要有一个小错误，但我不知道它在哪里。输出是 madifiddrdzaadamk。提前致谢。

Answer 1

这是我想出的解决方案。它会跟踪一次迷宫中访问过哪些单元格，但不会跟踪所有尝试。这可以通过使函数 return 成为 IEnumerable<string> 来完成，它将表示从迷宫中当前点到出口的路径。首先检查你是否离开了迷宫的边缘并且 return 没有。然后检查你是否在墙上，如果是，则没有路径 returned。否则，你检查你是否在边缘，如果是，你 return 仅由当前单元格表示的路径。然后您必须将当前单元格标记为已访问，然后尝试在 4 个方向中的每一个方向上查找所有路径，并将当前单元格连接到您找到的任何一个并产生它们。然后在最后将该单元格标记为未访问，以便它可以用于其他尝试。

private static IEnumerable<string> VisitCell(int row, int column, bool[,] visited)
{
    if (row < 0 || column < 0 || row >= maze.GetLength(0) || column >= maze.GetLength(1))
        yield break;

    if (maze[row, column] == '#' || visited[row, column])
        yield break;

    if (row == 0 || row == maze.GetLength(0) - 1 ||
        column == 0 || column == maze.GetLength(1) - 1)
    {
        yield return maze[row, column].ToString();
    }

    visited[row, column] = true;

    foreach (var path in VisitCell(row, column + 1, visited))
    {
        yield return maze[row, column] + path;
    }

    foreach(var path in VisitCell(row, column - 1, visited))
    {
        yield return maze[row, column] + path;
    }

    foreach (var path in VisitCell(row + 1, column, visited))
    {
        yield return maze[row, column] + path;
    }

    foreach (var path in VisitCell(row - 1, column, visited))
    {
        yield return maze[row, column] + path;
    }

    visited[row, column] = false;
}

那么你可以运行这个代码

private static char[,] maze =
{
    { 'a', '#', '#', 'k', 'm', '#' },
    { 'z', '#', 'a', 'd', 'a', '#' },
    { 'a', '*', 'm', '#', '#', '#' },
    { '#', 'd', '#', '#', '#', '#' },
    { 'r', 'i', 'f', 'i', 'd', '#' },
    { '#', 'd', '#', 'd', '#', 't' }
};

private static void Main(string[] args)
{
    foreach(var path in VisitCell(2, 1, new bool[6, 6]))
        Console.WriteLine(path);
}

得到这个结果

*madam

*madamk

*madk

*madkm

*a

*az

*aza

*difid

*dir

*did

您可以调整它以从每条路径的开头删除星号。

Answer 2

这是正确的代码：

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

public class Maze
{
    private const string InputFileName = "Labyrinth.in";
    private const string OutputFileName = "Labyrinth.out";

    public class Cell
    {
        public int Row { get; set; }
        public int Column { get; set; }

        public Cell(int row, int column)
        {
            this.Row = row;
            this.Column = column;
        }
    }

    private char[,] maze;
    private int size;
    private Cell startCell = null;

    public void ReadFromFile(string fileName)
    {
        using (StreamReader reader = new StreamReader(fileName))
        {
            // Read maze size and create maze
            this.size = int.Parse(reader.ReadLine());
            this.maze = new char[this.size, this.size];

            // Read the maze cells from the file
            for (int row = 0; row < this.size; row++)
            {
                string line = reader.ReadLine();
                for (int col = 0; col < this.size; col++)
                {
                    this.maze[row, col] = line[col];
                    if (line[col] == '*')
                    {
                        this.startCell = new Cell(row, col);
                    }
                }
            }
        }
    }

    public void FindAllPathsAndPrintThem()
    {
        if (this.startCell == null)
        {
            // Start cell is missing -> no path
            SaveResult(OutputFileName, "");
            return;
        }

        VisitCell(this.startCell.Row,
            this.startCell.Column, "");
    }

    private void VisitCell(int row, int column, string path)
    {
        if (row < 0 || column < 0 || row >= maze.GetLength(0) || column >= maze.GetLength(1))
        {
            return;
        }
        if (row < 0 || row > maze.GetLength(0) - 1 ||
            column < 0 || column > maze.GetLength(1) - 1)
        {
            SaveResult(OutputFileName, path);
            return;
        }

        if (this.maze[row, column] != '#')
        {
            // The cell is free --> visit it
            char x = this.maze[row, column];
            this.maze[row, column] = '#';
            VisitCell(row, column + 1, path + x);
            VisitCell(row, column - 1, path + x);
            VisitCell(row + 1, column, path + x);
            VisitCell(row - 1, column, path + x);
            this.maze[row, column] = x;
        }
    }

    public void SaveResult(string fileName, string result)
    {
        using (StreamWriter writer = new StreamWriter(fileName, true))
        {
            writer.WriteLine(result);
        }
    }

    static void Main()
    {
        Maze maze = new Maze();
        maze.ReadFromFile(InputFileName);
        maze.FindAllPathsAndPrintThem();
    }
}

关于我修改字符串的问题的评论是正确的，所以现在它起作用了，字符串没有在过程中被修改。

使用递归 DFS 打印迷宫中的所有可能路径

Print all possible paths in a labyrinth using recursive DFS

c#

algorithm

recursion

depth-first-search