C#，老鼠迷宫问题的回溯法求解（Rat in a Maze）算法与源代码

迷宫中的老鼠，作为另一个可以使用回溯解决的示例问题。

迷宫以块的N×N二进制矩阵给出，其中源块是最左上方的块，即迷宫[0][0]，目标块是最右下方的块，即迷宫[N-1][N-1]。老鼠从源头开始，必须到达目的地。老鼠只能朝两个方向移动：向前和向下。

在迷宫矩阵中，0表示该块是死胡同，1表示该块可用于从源到目标的路径。请注意，这是典型迷宫问题的简单版本。例如，更复杂的版本可以是rat可以在4个方向上移动，而更复杂的版本可以具有有限的移动次数。

算法：

（1）创建一个解决方案矩阵，最初用0填充。

（2）创建一个递归函数，该函数采用初始矩阵、输出矩阵和rat（i，j）的位置。

（3）如果位置超出矩阵或位置无效，则返回。

（4）将位置输出[i][j]标记为1，并检查当前位置是否为目标位置。如果到达目的地，打印输出矩阵并返回。

（5）递归调用位置（i+1，j）和（i，j+1）。

（6）取消标记位置（i，j），即输出[i][j]=0。

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

namespace Legalsoft.Truffer.Algorithm
{
	public static class Rat_In_Maze_Problem
	{
		private static bool Rate_In_Maze_IsSafe(int[,] maze, int x, int y)
		{
			int N = maze.GetLength(0);
			return (x >= 0 && x < N && y >= 0 && y < N && maze[x, y] == 1);
		}

		public static bool Rate_In_Maze_Solve(int[,] maze, out int[,] sol)
		{
			int N = maze.GetLength(0);
			sol = new int[N, N];
			if (Rate_In_Maze_Utility(maze, 0, 0,ref sol) == false)
			{
				return false;
			}
			return true;
		}

		private static bool Rate_In_Maze_Utility(int[,] maze, int x, int y,ref int[,] sol)
		{
			int N = maze.GetLength(0);
			if (x == N - 1 && y == N - 1 && maze[x, y] == 1)
			{
				sol[x, y] = 1;
				return true;
			}

			if (Rate_In_Maze_IsSafe(maze, x, y))
			{
				if (sol[x, y] == 1)
				{
					return false;
				}
				sol[x, y] = 1;
				if (Rate_In_Maze_Utility(maze, x + 1, y,ref sol))
				{
					return true;
				}
				if (Rate_In_Maze_Utility(maze, x, y + 1,ref sol))
				{
					return true;
				}
				if (Rate_In_Maze_Utility(maze, x - 1, y,ref sol))
				{
					return true;
				}
				if (Rate_In_Maze_Utility(maze, x, y - 1,ref sol))
				{
					return true;
				}
				sol[x, y] = 0;
				return false;
			}
			return false;
		}
	}
}