10、数据结构与算法C:迷宫算法

前言

以前玩好记心的时候有一个迷宫游戏,其中呢,就有一个答案,给出如何出迷宫,给的答案是最短路径。

当时想想还是很神奇的,但是呢,后来学了计算机后,其实就是通过计算机一步一步的是尝试,然后得到最短路径,然后通过ui给我们渲染出来。

正文

首先呢,要设置一个封闭的地图。

*

画完之后就是:

*

然后我们需要设置一些障碍:

我下面加上的障碍是:

*

蓝色部分为障碍,同时设置了终点。

然后我们开始一个探索思路:

1、 需要一个起点,这个起点需要做判断是否越界,然后同时需要判断是否该点就是封闭点;

2、 探路规则为先下,后右,然后上,做好左,如果都走不通,那么直接设置为该点走不通;

3、 设置终点的条件;

代码

主方法:

static void Main(string[] args)
{
	int[,] arr = new int[9,9];
	//形成一张封闭的地图
	for (int i = 0; i < 9; i++)
	{
		arr[0, i] = 1;
		arr[8, i]=1;
		arr[i, 0] = 1;
		arr[i, 8] = 1;
	}
	//设置一些障碍
	arr[3, 1] = 1;
	arr[3, 2] = 1;
	arr[5, 3] = 1;
	arr[5, 4] = 1;
	arr[6, 6] = 1;

	//显示该地图的情况
	Console.WriteLine("展示地图");
	showMap(arr);
	Console.WriteLine("开始探索地图");
	setWay(arr,1, 1);
	showMap(arr);
	Console.ReadKey();
}

方法函数:

/// <summary>
///  开始探路
/// </summary>
/// <param name="map"></param>
/// <param name="x"></param>
/// <param name="y"></param>
/// <returns></returns>
public static Boolean setWay(int[,] map,int x,int y)
{
	if (x > 8|| y > 8)
	{
		return false;
	}
	if (map[7,7]==2)
	{
		return true;
	}
	if (map[x, y] == 0)
	{
		//假设可以走过
		map[x, y] = 2;
		//那么向下走
		if (setWay(map, x + 1, y))
		{
			return true;
		}
		//向右走
		else if (setWay(map, x, y + 1))
		{
			return true;
		}
		//向上走
		else if (setWay(map, x - 1, y))
		{
			return true;
		}
		//向左走
		else if (setWay(map, x, y - 1))
		{
			return true;
		}
		else
		{
			//都走不通
			map[x, y] = 3;
			return false;
		}
	} 
	else
	{
		//没有走过
		return false;
	}
}

public static void showMap(int[,] map)
{
	for (int i = 0; i < 9; i++)
	{
		for (int j = 0; j < 9; j++)
		{
		  Console.Write(map[i,j] + " ");
		}
		Console.WriteLine("");
	}
}

运行结果:

*

总结

迷宫算法上面用递归实现,其实就是一个回溯问题。下一章,八皇后递归,之后就是图,也可以说是矩阵。

版权声明:本文不是「本站」原创文章,版权归原作者所有 | 原文地址: