DFS深搜经典算法

DFS深搜经典算法

输入样例：

5 4
1 1 2 1
1 1 1 1
1 1 2 1
1 2 1 1
1 1 1 2
1 1 4 3

输出：

7

代码：

#include
using namespace std;

int Endx, Endy;
int Min = 1000;
int map[100][100];//1是空地0是墙
int v[100][100];//访问数组0未访问7访问
void DFS(int x, int y, int step)//x，y表示当前坐标点
{
	if (x == Endx && y == Endy)//到达终点
	{
		if (step < Min)
		{
			Min = step;
		}
		return;
	}
	else//x，y不是终点:则开始试探
	{
		//顺时针右下左上试探
		if (map[x][y + 1] == 1 && v[x][y + 1] == 0)//向右
		{
			v[x][y + 1] = 7;//访问了
			DFS(x, y + 1, step + 1);
			v[x][y + 1] = 0;//回溯时设置为0未访问
		}
		if (map[x+1][y] == 1 && v[x+1][y] == 0)//向下
		{
			v[x+1][y] = 7;//访问了
			DFS(x+1, y, step + 1);
			v[x+1][y] = 0;//回溯时设置为0未访问
		}
		if (map[x][y - 1] == 1 && v[x][y - 1] == 0)//向左
		{
			v[x][y - 1] = 7;//访问了
			DFS(x, y - 1, step + 1);
			v[x][y - 1] = 0;//回溯时设置为0未访问
		}
		if (map[x - 1][y] == 1 && v[x - 1][y] == 0)//向上
		{
			v[x - 1][y] = 7;//访问了
			DFS(x - 1, y, step + 1);
			v[x - 1][y] = 0;//回溯时设置为0未访问
		}
		return;
	}
}

int main()
{
	int m, n;
	cin >> m >> n;

	for (int i = 1; i <= m; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			cin >> map[i][j];//1是空地，0是障碍
		}
	}

	int Beginx, Beginy;
	cin >> Beginx >> Beginy >> Endx >> Endy;

	v[Beginx][Beginy] = 7;
	DFS(Beginx, Beginy, 0);

	cout << Min;

	return 0;
}