题解 | #迷宫问题#

using System;
using System.Collections.Generic;
using System.Linq;

namespace HJ43
{
    internal class Program
    {

        public class Point
        {
            public int X { get; set; }
            public int Y { get; set; }

            public Point Father { get; set; }

            public Point() { }

            public Point(int x, int y)
            {
                X = x;
                Y = y;
            }

            public Point(int x, int y, Point point)
            {
                X = x;
                Y = y;
                Father = point;
            }

            public override string ToString()
            {
                return $"({X},{Y})";
            }
        }


        static void Main(string[] args)
        {
            var inputStr = Console.ReadLine();
            var stringArr = inputStr.Split();

            int m = int.Parse(stringArr[0]);
            int n = int.Parse(stringArr[1]);

            int[,] ints = new int[m, n];

            for (int i = 0; i < m; i++)
            {
                var strs = Console.ReadLine().Split();
                for (int j = 0; j < n; j++)
                {
                    ints[i, j] = int.Parse(strs[j]);
                }
            }

            bool[,] isVisited = new bool[m, n];

            List<Point> path = new List<Point>();

            //if (DeepthFirstSearch(ints, isVisited, 0, 0, path))
            //{
            //    foreach (Point p in path)
            //    {
            //        Console.WriteLine(p);
            //    }
            //}

            Point finalPoint = BreadthFirstSearch(ints, isVisited, 0, 0, path);
            if (finalPoint != null)
            {
                List<Point> points = new List<Point>();
                points.Add(finalPoint);
                Point father = finalPoint.Father;
                while (true)
                {
                    if (father == null)
                    {
                        break;
                    }
                    //从终点往起点方向加入路径点
                    points.Add(father);
                    father = father.Father;
                }

                //回为加入时是从终点加入，因此需要倒置输出
                points.Reverse();

                foreach (Point point in points)
                {
                    Console.WriteLine(point);
                }
            }
        }

        /// <summary>
        /// 深度优先搜索，从一个点一直往下层走，不断往树的叶的方向走
        /// </summary>
        static bool DeepthFirstSearch(int[,] map, bool[,] isVisited, int x, int y, List<Point> path)
        {
            path.Add(new Point(x, y));
            while (true)
            {
                if (x == map.GetLength(0) - 1 && y == map.GetLength(1) - 1)
                {
                    return true;
                }

                //假如向下能走并且下边的点没有被访问过，向下走
                if (x + 1 < map.GetLength(0) && map[x + 1, y] == 0 && isVisited[x + 1, y] == false)
                {
                    x = x + 1;
                    path.Add(new Point(x, y));
                    //从这个点开始下一步搜索，同时将这个点标记为访问过，防止下个点搜索后回到这个点
                    isVisited[x, y] = true;
                    continue;
                }

                //假如向右能走并且右边的点没有被访问过，向右走
                if (y + 1 < map.GetLength(1) && map[x, y + 1] == 0 && isVisited[x, y + 1] == false)
                {
                    y = y + 1;
                    path.Add(new Point(x, y));
                    //从这个点开始下一步搜索，同时将这个点标记为访问过，防止下个点搜索后回到这个点
                    isVisited[x, y] = true;
                    continue;
                }

                //假如向上能走并且上边的点没有被访问过，向上走
                if (x - 1 >= 0 && map[x - 1, y] == 0 && isVisited[x - 1, y] == false)
                {
                    x = x - 1;
                    path.Add(new Point(x, y));
                    //从这个点开始下一步搜索，同时将这个点标记为访问过，防止下个点搜索后回到这个点
                    isVisited[x, y] = true;
                    continue;
                }

                //假如向左能走并且左边的点没有被访问过，向左走
                if (y - 1 >= 0 && map[x, y - 1] == 0 && isVisited[x, y - 1] == false)
                {
                    y = y - 1;
                    path.Add(new Point(x, y));

                    //从这个点开始下一步搜索，同时将这个点标记为访问过，防止下个点搜索后回到这个点
                    isVisited[x, y] = true;
                    continue;
                }
                //上下左右都不能走时，回退一步，
                //由于之前这条路径上的点都被标记访问过，因此不会再走这条路径
                path.RemoveAt(path.Count - 1);

                //如果多次深入搜索之后都没有路径，且最后回退到起始点，说明没用路径；
                if (path.Count == 1)
                {
                    return false;
                }

                x = path.Last().X;
                y = path.Last().Y;


            }
        }


        /// <summary>
        /// 广度优先搜索，从树的一层层去搜索，搜索完成一层再下一层
        /// </summary>
        static Point BreadthFirstSearch(int[,] map, bool[,] isVisited, int x, int y, List<Point> path)
        {
            path.Add(new Point(x, y));
            Point p = null;
            while (true)
            {
                //无解，退出
                if (path.Count == 0)
                {
                    return null;
                }
                p = path[0];
                path.RemoveAt(0);
                x = p.X;
                y = p.Y;

                if (x == map.GetLength(0) - 1 && y == map.GetLength(1) - 1)
                {
                    return p;
                }

                //假如向下能走并且下边的点没有被访问过，加入进来
                if (x + 1 < map.GetLength(0) && map[x + 1, y] == 0 && isVisited[x + 1, y] == false)
                {
                    path.Add(new Point(x + 1, y, p));
                    //将这个点标记为访问过，防止下个点搜索后再次加入这个点，保证每个点只被加入一次
                    isVisited[x + 1, y] = true;
                }

                //假如向右能走并且右边的点没有被访问过，加入进来
                if (y + 1 < map.GetLength(1) && map[x, y + 1] == 0 && isVisited[x, y + 1] == false)
                {
                    path.Add(new Point(x, y + 1, p));
                    //将这个点标记为访问过，防止下个点搜索后再次加入这个点，保证每个点只被加入一次
                    isVisited[x, y + 1] = true;

                }

                //假如向上能走并且上边的点没有被访问过，加入进来
                if (x - 1 >= 0 && map[x - 1, y] == 0 && isVisited[x - 1, y] == false)
                {
                    path.Add(new Point(x - 1, y, p));
                    //将这个点标记为访问过，防止下个点搜索后再次加入这个点，保证每个点只被加入一次
                    isVisited[x - 1, y] = true;
                }

                //假如向左能走并且左边的点没有被访问过，加入进来
                if (y - 1 >= 0 && map[x, y - 1] == 0 && isVisited[x, y - 1] == false)
                {
                    path.Add(new Point(x, y - 1, p));
                    //将这个点标记为访问过，防止下个点搜索后再次加入这个点，保证每个点只被加入一次
                    isVisited[x, y - 1] = true;
                }

            }
        }
    }
}