啊哈算法 走迷宫 小哼找小哈 DFS

迷宫：n行m列的单元格

单元格要么是空地，要么是障碍物。

这里n,m最大不超过50.

程序如下：

// maze6.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>

using namespace std;

int n, m;//n行，m列
int p, q;
int min = INT_MAX;

int maze[51][51];//迷宫矩阵
int book[51][51];//记录是否访问标记矩阵

void dfs(int x, int y, int step)
{
	//四个方向
	int next[4][2] = { { 0, 1 },//向右走
	{ 1, 0 },//向下走
	{ 0, -1 },//向左走
	{ -1, 0 } };//向上走


	int tx, ty, k;
	//判断是否到达小哈的位置
	if (x == p&&y == q)
	{//进入循环，表示找到小哈
		//更新最小值
		if (step < min)
		{
			min = step;
		}
		return;//返回，这里很重要
	}

	//枚举四种走法

	for (k = 0; k <= 3; k++)
	{
		//计算下一个点的坐标
		tx = x + next[k][0];
		ty = y + next[k][1];
		//判断是否越界
		if (tx<1 || tx>n || ty<1 || ty>m)
		{
			continue;//没有越界，继续往下走。
		}
		//判断该点是否为障碍物后者已经在路径中。
		if (maze[tx][ty] == 0 && book[tx][ty] == 0)
		{
			book[tx][ty] = 1;//标记这个点已经走过
			dfs(tx, ty, step + 1);//开始尝试下一个点
			book[tx][ty] = 0;//尝试结束，取消这个点的标记
		}
	}

}


int _tmain(int argc, _TCHAR* argv[])
{
	int i, j, startx, starty;
	cout << "行数，列数" << endl;
	cin >> n >> m;
	cout << "请输入行数，列数值" << endl;

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			cin >> maze[i][j];
		}
	}
	cout << "请输入起始点(1,1)为最初的点" << endl;
	cin >> startx >> starty;
	cout << "请输入终点" << endl;
	cin >> p >> q;

	dfs(startx, starty, 0);
	cout <<"最短步数" <<min << endl;

	system("pause");
	return 0;
}