老鼠迷宫问题递归解法

痛定思痛。 2022-11-15 11:46 201阅读 0赞

迷宫如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9fc2hpeGlvbmc_size_16_color_FFFFFF_t_70]  
不是最优解，仅供参考！

using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;
    
    /* * * 老鼠迷宫问题：有一个迷宫，在迷宫的某个出口放着一块奶酪。将一只老鼠由某个入口处放进去，它必须穿过迷宫，找到奶酪。请找出它的行走路径。 * 9*9自定义迷宫 * */
    
    namespace MouseMazeTest
    { 
        class Program
        { 
    
            public static int[,] maze = new int[9, 9] { 
                { 0, 0, 0, 1, 0, 0, 0, 1, 1 },
                { 0, 1, 1, 1, 0, 0, 0, 1, 1 },
                { 0, 1, 0, 0, 0, 0, 0, 0, 0 },
                { 1, 1, 1, 1, 1, 1, 1, 0, 0 },
                { 0, 1, 0, 0, 0, 0, 1, 0, 0 },
                { 0, 1, 0, 0, 1, 1, 1, 0, 0 },
                { 0, 1, 0, 0, 1, 0, 0, 1, 0 },
                { 0, 1, 0, 1, 1, 1, 1, 1, 1 },
                { 0, 1, 0, 0, 0, 0, 0, 0, 0 }
            };
    
            static void Main(string[] args)
            { 
                FindWay(maze, 0, 3, 7, 8);
            }
    
            public static void FindWay(int[,] maze, int sx, int sy, int ex, int ey)
            { 
                List<string> way = new List<string>();
    
                if (FindWay(way, maze, sx, sy, ex, ey))
                { 
                    Console.WriteLine("找到路了！");
                    foreach (string str in way)
                        Console.Write(str + "-");
                    Console.WriteLine("");
                }
                else
                { 
                    foreach (string str in way)
                        Console.Write(str + "-");
                    Console.WriteLine("没找到啊！");
                }
    
                Console.ReadLine();
            }
    
            public static bool FindWay(List<string> way, int[,] maze, int sx, int sy, int ex, int ey)
            { 
                way.Add(sx+","+sy);
    
                if (sx == ex && sy == ey)
                    return true;
                else if (sx - 1 > -1 && maze[sx - 1, sy] == 1 && !way.Contains((sx - 1) +"," + sy) && FindWay(way, maze, sx - 1, sy, ex, ey))
                    return true;
                else if (sy - 1 > -1 && maze[sx, sy - 1] == 1 && !way.Contains(sx +"," + (sy - 1)) && FindWay(way, maze, sx, sy - 1, ex, ey))
                    return true;
                else if (sx + 1 < 9 && maze[sx + 1, sy] == 1 && !way.Contains((sx + 1) +"," + sy) && FindWay(way, maze, sx + 1, sy, ex, ey))
                    return true;
                else if (sy + 1 < 9 && maze[sx, sy + 1] == 1 && !way.Contains(sx +"," + (sy + 1)) && FindWay(way, maze, sx, sy + 1, ex, ey))
                    return true;
                else
                    way.Remove(sx + "," + sy);
                return false;
            }
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9fc2hpeGlvbmc_size_16_color_FFFFFF_t_70]: /images/20221022/30156bf09d61414ab733763ffd3597c0.png