迷宫问题一 找到迷宫的一条路径（DFS+回溯）

问题描述：

一天,小明不小心进入了一个迷宫,现在请你帮助他判断能否出走出迷宫,如果可能,则输出YES. 如果不能走到出口,则输出NO. 每次走只能是上下左右4个方向.

*表示可走

#表示障碍

T表示出口

入口是（1,1），数据保证左上角是入口

#include
  
   
using namespace std;
char maze[100][100];
bool flag[100][100];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
int m,n;
bool dfs(int x,int y)
{
	flag[x][y]=1;              //走过的路标记为1
	if(maze[x][y]=='T')return true;
	for(int i=0;i<4;i++)       //四个方向
	{
		int nx=x+dx[i];
		int ny=y+dy[i];
		if(flag[nx][ny]==0||maze[nx][ny]=='*'||maze[nx][ny]=='T'&&nx>0&&ny>0&&nx
   
    >m>>n){ memset(maze,0,sizeof(maze)); memset(flag,0,sizeof(flag)); for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) cin>>maze[i][j]; if(dfs(1,1))cout<<"YES"<
    
     测试数据： 
     
3 3
 
     
*##





 
     
***
 
     
##T
 
     
4 4
 
     
****
 
     
*##*
 
     
**#*
 
     
###T