博客

题目描述

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