网站开发资金规模,it行业做网站一个月多少钱,怎样在网站做两份简历,网站一直没有收录1 老鼠迷宫问题
迷宫中的老鼠#xff0c;作为另一个可以使用回溯解决的示例问题。
迷宫以块的NN二进制矩阵给出#xff0c;其中源块是最左上方的块#xff0c;即迷宫[0][0]#xff0c;目标块是最右下方的块#xff0c;即迷宫[N-1][N-1]。老鼠从源头开始#xff0c;必须…
1 老鼠迷宫问题
迷宫中的老鼠作为另一个可以使用回溯解决的示例问题。
迷宫以块的N×N二进制矩阵给出其中源块是最左上方的块即迷宫[0][0]目标块是最右下方的块即迷宫[N-1][N-1]。老鼠从源头开始必须到达目的地。老鼠只能朝两个方向移动向前和向下。
在迷宫矩阵中0表示该块是死胡同1表示该块可用于从源到目标的路径。请注意这是典型迷宫问题的简单版本。例如更复杂的版本可以是rat可以在4个方向上移动而更复杂的版本可以具有有限的移动次数。 2 老鼠迷宫问题的回溯法求解
1创建一个解决方案矩阵最初用0填充。
2创建一个递归函数该函数采用初始矩阵、输出矩阵和ratij的位置。
3如果位置超出矩阵或位置无效则返回。
4将位置输出[i][j]标记为1并检查当前位置是否为目标位置。如果到达目的地打印输出矩阵并返回。
5递归调用位置i1j和ij1。
6取消标记位置ij即输出[i][j]0。
3 源程序
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; } } } 4 源代码
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;}}
}
