迷宫问题【深搜学习】

输入：

第一行有两个数m,n，m代表迷宫的行，n代表迷宫的列。

接下来的n行m列为迷宫，0表示空地，1表示障碍物，

最后一行4个数，前两个是迷宫入口的坐标，后两个是目的地的坐标

eg：

input：

5 4

0 0 1 0

0 0 0 0

0 0 1 0

0 1 0 0

0 0 0 1

1 1 4 3

output：

7 

#include<iostream>
using namespace std;
int a[100][100];
int book[100][100] = {0};
int tx,ty;
int p,q;   //the position of the destination
int m,n;   //the size of the maze
int next[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};
int mina = 999999;
void dfs(int dx,int dy,int step)
{
	if((dx == p) && (q == dy))
	{
		if(mina > step)
		{
			mina = step;
		}
		return ;
	}
	for(int i = 0;i < 4;i++)
	{
		tx = dx + next[i][0];
		ty = dy + next[i][1];
		if((tx < 1)|| (ty < 1) || (tx > m) || (ty > n))
		{
			continue ;
		}
		if((0 == a[tx][ty]) && (0 == book[tx][ty]))
		{
			book[tx][ty] = 1;
			dfs(tx,ty,step+1);
			book[tx][ty] = 0;
		}	
    }
    return ;
}

int main()
{
    int x,y;   //the position of the outset
	cin >> m >> n;
	for(int i = 1;i <= m;++i)
	{
		for(int j = 1;j <= n;++j)
		{
			cin >> a[i][j];
		}
	}
	cin >> x >> y >> p >> q;
	book[x][y] = 1;
	dfs(x,y,0);
	cout << mina<<endl;
	return 0;
}