蓝桥杯备赛 Day13.1走出迷宫

链接：走出迷宫
题目描述

小明现在在玩一个游戏，游戏来到了教学关卡，迷宫是一个N*M的矩阵。

小明的起点在地图中用“S”来表示，终点用“E”来表示，障碍物用“#”来表示，空地用“.”来表示。

障碍物不能通过。小明如果现在在点（x，y）处，那么下一步只能走到相邻的四个格子中的某一个：（x+1，y），（x-1，y），（x，y+1），（x，y-1）；

小明想要知道，现在他能否从起点走到终点。

输入描述:

本题包含多组数据。
每组数据先输入两个数字N,M
接下来N行，每行M个字符，表示地图的状态。
数据范围：
2<=N,M<=500
保证有一个起点S，同时保证有一个终点E.

输出描述:

每组数据输出一行，如果小明能够从起点走到终点，那么输出Yes，否则输出No

示例1

输入

3 3
S..
..E
...
3 3
S##
###
##E

输出

Yes
No

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;const int N = 6e2 + 10;
char g[N][N];
int m, n;
int sx, sy, tx, ty;
int vis[N][N];
//去掉不必要的第一个元素
int dx[] = { 0, 1, -1, 0 };
int dy[] = { 1, 0, 0, -1 };struct point {int x, y;
};
int flag = 0;void bfs(point p) {queue<point> q;q.push(p);vis[p.x][p.y] = 1;while (!q.empty()) {point cur = q.front();q.pop();if (cur.x == tx && cur.y == ty) {flag = 1;return;}for (int i = 0; i < 4; i++) {int x = cur.x + dx[i];int y = cur.y + dy[i];// 增加边界检查if (x >= 1 && x <= n && y >= 1 && y <= m && (g[x][y]=='.'|| g[x][y] == 'E') && vis[x][y] != 1) {q.push({ x, y });vis[x][y] = 1;}}}
}
int main() {while (cin >> n >> m) {flag = 0;memset(vis, 0, sizeof vis);for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {cin >> g[i][j];if (g[i][j] == 'S') {sx = i;sy = j;}if (g[i][j] == 'E') {tx = i;ty = j;}}}bfs({ sx, sy });if (flag == 1) cout << "Yes" << endl;else cout << "No" << endl;}return 0;
}