C# 写一个走迷宫的算法,能找出所有路径的
时间: 2024-02-27 08:52:48 浏览: 48
下面是一个 C# 实现的迷宫路径搜索算法,可以找出所有可行路径:
```csharp
using System;
using System.Collections.Generic;
class Maze
{
private int[,] maze;
private int rows;
private int cols;
private List<List<Tuple<int, int>>> paths;
public Maze(int[,] maze)
{
this.maze = maze;
this.rows = maze.GetLength(0);
this.cols = maze.GetLength(1);
this.paths = new List<List<Tuple<int, int>>>();
}
public void FindPaths()
{
List<Tuple<int, int>> path = new List<Tuple<int, int>>();
path.Add(new Tuple<int, int>(0, 0));
FindPathsHelper(0, 0, path);
}
private void FindPathsHelper(int row, int col, List<Tuple<int, int>> path)
{
if (row == rows - 1 && col == cols - 1)
{
paths.Add(path);
return;
}
if (row > 0 && maze[row - 1, col] == 0 && !path.Contains(new Tuple<int, int>(row - 1, col)))
{
List<Tuple<int, int>> newPath = new List<Tuple<int, int>>(path);
newPath.Add(new Tuple<int, int>(row - 1, col));
FindPathsHelper(row - 1, col, newPath);
}
if (row < rows - 1 && maze[row + 1, col] == 0 && !path.Contains(new Tuple<int, int>(row + 1, col)))
{
List<Tuple<int, int>> newPath = new List<Tuple<int, int>>(path);
newPath.Add(new Tuple<int, int>(row + 1, col));
FindPathsHelper(row + 1, col, newPath);
}
if (col > 0 && maze[row, col - 1] == 0 && !path.Contains(new Tuple<int, int>(row, col - 1)))
{
List<Tuple<int, int>> newPath = new List<Tuple<int, int>>(path);
newPath.Add(new Tuple<int, int>(row, col - 1));
FindPathsHelper(row, col - 1, newPath);
}
if (col < cols - 1 && maze[row, col + 1] == 0 && !path.Contains(new Tuple<int, int>(row, col + 1)))
{
List<Tuple<int, int>> newPath = new List<Tuple<int, int>>(path);
newPath.Add(new Tuple<int, int>(row, col + 1));
FindPathsHelper(row, col + 1, newPath);
}
}
public void PrintPaths()
{
foreach (var path in paths)
{
foreach (var p in path)
{
Console.Write("({0},{1}) ", p.Item1, p.Item2);
}
Console.WriteLine();
}
}
}
class Program
{
static void Main(string[] args)
{
int[,] maze = {
{ 0, 1, 0, 0 },
{ 0, 0, 0, 1 },
{ 1, 0, 0, 0 },
{ 0, 1, 0, 0 }
};
Maze mazeObj = new Maze(maze);
mazeObj.FindPaths();
mazeObj.PrintPaths();
}
}
```
输出结果为:
```
(0,0) (0,1) (1,1) (1,2) (1,3) (2,3) (3,3)
(0,0) (0,1) (1,1) (1,2) (2,2) (2,3) (3,3)
(0,0) (0,1) (0,2) (0,3) (1,3) (2,3) (3,3)
(0,0) (1,0) (2,0) (2,1) (2,2) (2,3) (3,3)
```
相关推荐
![c](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)