dfs迷宫问题模板

/*输入起点终点坐标，输入迷宫，输出最短路
深搜思想：不撞墙不回头，每次走到下一步都有n种情况，遍历这n种情况，
对于每种情况到达的下一步，又有n种情况可以走，
*/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#define N 100

using namespace std;

int map[N][N] = { 0 },vis[N][N];
int endx, endy, m, n;
int min = 9999;

int dx[4] = { -1,0,0,1 };
int dy[4] = { 0,-1,1,0 };

void dfs(int x, int y, int step)
{
	if (x == endx && y == endy)
	{
		if (step < min)
			min = step;
		return;
	}
	for (int i = 0; i <= 3; i++)
	{
		int tx = x + dx[i];
		int ty = y + dy[i];
		if (!vis[tx][ty] && tx >= 1 && tx <= m && ty >= 1 && ty <= n && map[tx][ty] == 0)
		{
			vis[tx][ty] = 1;
			dfs(tx, ty, step + 1);
			vis[tx][ty] = 0;
		}
	}
	return;
}

int main()
{
	int startx, starty;
	int i, j;
	scanf("%d%d", &m, &n);//m行n列
	for (int i = 1; i <= m; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			scanf("%d", &map[i][j]);
		}
	}
	scanf("%d%d%d%d", &startx, &starty, &endx, &endy);
	vis[startx][starty] = 1;
	dfs(startx,starty,0);//深搜需要传递的量有当前位置，以及对应已经走得步数
	printf("%d\n", min);
	return 0;
}