题解 | 迷宫寻路 c# 递归+非递归

using System;
using System.Collections.Generic;
using System.Linq;
public class Program {
    public static void Main() {
        int[] inputs = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
        int n = inputs[0];
        int m = inputs[1];
        List<List<char>> maze = new List<List<char>>();
        for (int i = 0; i < n; i++) {
            maze.Add(Console.ReadLine().ToCharArray().ToList());
        }
        bool[,] visited = new bool[n, m]; //用来储存哪些格子已经被走过了
        Random random = new Random();
        int randomInRange = random.Next(-10, 11);
        //随机调用两种DFS方法
        if (randomInRange >= 0) {
            Console.WriteLine(DFSMazeRecusive(maze, visited, 0, 0, n, m));
        } else {
            Console.WriteLine(DFSMazeNotRecusive(maze, visited, 0, 0, n, m));
        }
    }


    //DFS迷宫寻路,递归写法，左上角（1,1）为起点，右下角（n,m）为终点。变量迷宫maze和Visted数组还有r，c，n，m都不用作为全局变量定义在类变量中，只需要在每次递归的时候作为参数重新传给DFS函数即可
    public static string DFSMazeRecusive(List<List<char>> maze, bool[,] visited,
                                         int r,
                                         int c, int n, int m) {
        //到达终点的条件
        if (r == n - 1 && c == m - 1) {
            return "Yes";
        }

        //当前走的格子设置为True
        visited[r, c] = true;

        //没有到达终点，则向四个方向走，上下左右
        int[] directionR = {-1, 1, 0, 0 };
        int[] directionC = {0, 0, -1, 1 };
        //遍历四种走的方向，看哪个方向是可以走的
        for (int i = 0; i < 4; i++) {
            int nextR = r + directionR[i];
            int nextC = c + directionC[i];
            //判断下个方向可不可以走的条件是，不能超过迷宫边界（nextR >= 0 && nextC >= 0 && nextR < n && nextC < m），下个方向上的格子是'.'（maze[nextR][nextC] == '.'），且没有被走过（!visited[nextR, nextC]）
            if (nextR >= 0 && nextC >= 0 && nextR < n && nextC < m &&
                    maze[nextR][nextC] == '.' && !visited[nextR, nextC]) {
                if (DFSMazeRecusive(maze, visited, nextR, nextC, n, m) == "Yes")
                    return "Yes";//递归
            }
        }

        //如果到达终点的条件和向下一个格子走的条件没有触发，说明这个迷宫走不到终点，返回NO
        return "No";
    }

    //非递归写法，用stack，这里的bool[,] visited, int r, int c, int n, int m传入参数其实都是不必要的，但是懒得改了
    public static string DFSMazeNotRecusive(List<List<char>> maze, bool[,] visited,
                                            int r, int c, int n, int m) {
        Stack<int[]> stack = new
        Stack<int[]>();//非递归法要用Stack来装下一个走到的格子，模拟系统的调用栈
        visited[0, 0] =
            true; //visited数组用来记录哪些格子走过了，防止重复入栈
        int[] ori = {0, 0};
        stack.Push(ori);//起点入栈

        //定义四种方向
        int[] directionR = { -1, 1, 0, 0 };
        int[] directionC = { 0, 0, -1, 1 };

        while (stack.Count >
                0) { //若stack长度为0了，说明在走到终点之前就没有可走的格子了，说明终点不可达
            //出栈,走到当前位置，如果一直出栈就说明当前道路往上下左右都走不通，要一直往回走
            int[] coor = stack.Pop();
            int row = coor[0];
            int col = coor[1];

            if (row == n - 1 && col == m - 1) //到达终点
                return "Yes";

            for (int i = 0; i < 4; i++) {
                int nextR = row + directionR[i];
                int nextC = col + directionC[i];
                //依旧是判断下一个格子能不能走
                if (nextR >= 0 && nextC >= 0 && nextR < n && nextC < m &&
                        maze[nextR][nextC] == '.' && !visited[nextR, nextC]) {
                    visited[nextR, nextC] = true;
                    int[] nextCoor = { nextR, nextC };
                    stack.Push(nextCoor);//入栈
                }
            }
        }
        return "No";
    }
}