济南建设网站平台天津黑曼巴网站建设

题目描述
​ 小明刚刚参加完期中考试，“这次又能得班级第一了”，他沾沾自喜，想起之前一直努力学习的自己，他决定去西城红场看个电影放松一下。现在小明想从学校走到电影院，因为市政大力修路和挖地铁，有些道路不允许步行，请判断小明能否走到电影院（只能朝上下左右四个方向行走），如果能到，则输出最短步数，如果不能到，则输出 No。

输入
​ 第 1 行两个数 n 和 m 表示地图有 n 行 m 列 2≤n,m≤500​ 第 2 行至第 n+1 行为地图，其中 s 表示学校 g 表示电影院​ . 为步行可以通过的点 # 为步行不可通过的点

输出
​ 能走到电影院输出最少步数​ 不能走到电影院输出 No
样例输入1
4 5
s####
…#

#…g
样例输出1
No
样例输入2
4 4
…s
…##
…
.g…
样例输出2
5

#include<iostream>
#include<queue>
using namespace std;struct node {int x, y, cnt;
};
int dir[4][2] = { 0,1,1,0,0,-1,-1,0 };
int main() {int n, m;cin >> n >> m;char map[505][505];queue<node> que;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> map[i][j];if (map[i][j] == 's') {que.push({ i,j,0 });}}}while (!que.empty()) {node temp = que.front();que.pop();for (int i = 0; i < 4; i++) {int x = temp.x + dir[i][0];int y = temp.y + dir[i][1];if (map[x][y] == 'g') {cout << temp.cnt + 1 << endl;return 0;}if (map[x][y] == '.') {que.push({ x, y,temp.cnt + 1 });map[x][y] = '#';}}}cout << "No" << endl;return 0;
}