题解 | #走出迷宫#

bfs广度搜索，判断能否走出去，直接求解他的最短路径即可.若不存在这样的路径，则不能走出去 ；否则可以走出去

int mov[4][4] = { {1,0},{-1,0},{0,1},{0,-1}}；
//对于某一个可移动的点，一共有前后左右四个移动方向。
int n, m;
int spos, epos;
//记录初始位置，末尾位置
char sav[600][600];//迷宫字符矩阵
bool vis[600][600]={0};
//判断某个点是否走过
queue<int> das;//储存分解的队列
bool judge(int x, int y)
{
	return x >= 0 && y >= 0 && x <= n - 1 && y <= m - 1;
    判断是否在迷宫之内
}
bool bfs(int x, int y)
{
	/*memset(vis, -1, sizeof(vis));*/
	vis[x][y] = 1;初始地址，直接让他走过
	das.push(x*m+y);将初始位置丢进去，等待分解。
    
    
    //如果队列不为空，表明队列中的那个点，还能继续找下一个点。
    如果队列中的点，不能走到终点了，在一轮循环之中，它就会被删除，而对其他的没有什么影响
	while ( !das.empty() )
	{
		int xx= das.front()/m;
		int yy = das.front() % m;
		das.pop();
		for ( int i = 0; i < 4; i++ )
		{
			int dx = xx + mov[i][0];
			int dy = yy + mov[i][1];
            //得到下一个可能的位置，并进行有效性判断
			if ( judge(dx, dy) && !vis[dx][dy]&&sav[dx][dy]!='#' )
			{
//                 cout<<dx<<" "<<dy<<endl;
				vis[dx][dy] = 1;
                //将（x，y）相邻的下一个点丢进队列之中等待分解
				das.push(dx * m + dy);
				if ( dx * m + dy == epos )
					return true;
                    //如果这个点是终点，就直接返回1，代表找到了
			}
		}
	}
	return false;
}
int main(int arg, char** argv) {
	/*ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin.tie(nullptr);*/
	
	while(cin >> n >> m){
    memset(vis,0,sizeof(vis));
    while(!das.empty())
    {
        das.pop();
    }//多组测试样例，删除上一组样例剩下的东西
	ifor(i, 0, n-1)
	{
		ifor(j, 0, m-1)
		{
			cin >> sav[i][j];
			if ( sav[i][j] == 'S' )
				spos = i * m + j;
			if ( sav[i][j] == 'E' )
				epos = i * m + j;
		}
	}
	if ( bfs(spos / m, spos % m) )
		cout << "Yes"<<endl;
	else cout << "No"<<endl;
    }
	return 0;
}