迷宫找路

小技巧：用scanf(" %c",&map[i][j])读入字符,这里%c前加了空格可以过滤掉字符前的回车和空格，没有回车空格也不影响。 这里最好用BFS的原因：bfs找到终点直接break就好了，而dfs找到终点依旧得回溯。 坚持用DFS的话要注意的细节：回溯的时候visit[]不清空。 因为这里只是找终点而不是求最短路，走过的路没必要继续走了，因为这条路要是能到终点你就已经找到了路，这条路要是到不了终点也没必要走。 DFS

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int N,M;
char map[1010][1010];
int visit[1010][1010];
bool flag;
int dir[4][2]={{-1,0},{0,-1},{1,0},{0,1}};//上左下右 

void dfs(int x,int y)
{
	if(map[x][y]=='E'){
		flag=true;return;
	}
	for(int i=0;i&lt;4;i++)//各个方向走一遍 
	{
		int xx=x+dir[i][0];
		int yy=y+dir[i][1];
		if(map[xx][yy]!='#' &amp;&amp; !visit[xx][yy] &amp;&amp; xx&gt;=1 &amp;&amp; yy&gt;=1 &amp;&amp; xx&lt;=N &amp;&amp; y&lt;=M)//能走，不出地图,没走过 
		{
			visit[xx][yy]=1;dfs(xx,yy);
		}
	}
	return ;
}

int main()
{
	while(cin&gt;&gt;N&gt;&gt;M)
	{
		memset(map,0,sizeof(map));//清空地图，这个很important
		memset(visit,0,sizeof(visit));//清空标记数组 
		int x=-1,y=-1;//出发点 
		flag=false;
		for(int i=1;i&lt;=N;i++){//构建地图 
			for(int j=1;j&lt;=M;j++){
				scanf(" %c",&amp;map[i][j]);
				if(map[i][j]=='S'){
					x=i;y=j;
				}
			}
		}
		dfs(x,y);
		if(flag)	cout&lt;&lt;"Yes"&lt;<endl; else cout<<"no"<<endl; } return 0; ``` **bfs** #include<iostream>
#include<cstring>
#include<queue>
using namespace std;
char mp[505][505];
int visit[505][505];
bool flag;
int N,M;
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
struct Point{
	int x,y;
};

bool bfs(int x,int y)
{
	queue<point> q;
	q.push({x,y});
	while(!q.empty())
	{
		int xa=q.front().x;
		int xb=q.front().y;
		q.pop();
		for(int i=0;i&lt;4;i++)
		{
			int xx=xa+dir[i][0];
			int yy=xb+dir[i][1];
			if(mp[xx][yy]=='E')	return true;
			if(mp[xx][yy]!='#' &amp;&amp; !visit[xx][yy] &amp;&amp; xx&gt;0 &amp;&amp; yy&gt;0 &amp;&amp; xx&lt;=N &amp;&amp;yy&lt;=M)
			{
				visit[xx][yy]=1;
				q.push({xx,yy});
			}
		}
	}
	return false;
}

int main()
{
	while(cin&gt;&gt;N&gt;&gt;M)
	{
		int x,y;
		flag=false;
		memset(mp,0,sizeof(mp));
		memset(visit,0,sizeof(visit));
		for(int i=1;i&lt;=N;i++)
		{
			for(int j=1;j&lt;=M;j++)
			{
				scanf(" %c",&amp;mp[i][j]);
				if(mp[i][j]=='S'){
					x=i;y=j;
				}
			}
		}
		flag=bfs(x,y);
		if(flag)	cout&lt;&lt;"Yes"&lt;</point></queue></cstring></endl;></cstring></cstdio></iostream>