信息学奥赛一本通 c++ 1252：走迷宫

60 阅读 0 评论 40 点赞

我是靠谱客的博主着急饼干，最近开发中收集的这篇文章主要介绍信息学奥赛一本通 c++ 1252：走迷宫，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

1252：走迷宫

时间限制: 1000 ms 内存限制: 65536 KB
提交数: 16598 通过数: 7523

【题目描述】

一个迷宫由R行C列格子组成，有的格子里有障碍物，不能走；有的格子是空地，可以走。

给定一个迷宫，求从左上角走到右下角最少需要走多少步(数据保证一定能走到)。只能在水平方向或垂直方向走，不能斜着走。

【输入】

第一行是两个整数，Ｒ和Ｃ，代表迷宫的长和宽。（ 1<= R，C <= 40)

接下来是Ｒ行，每行Ｃ个字符，代表整个迷宫。

空地格子用‘.’表示，有障碍物的格子用‘#’表示。

迷宫左上角和右下角都是‘.’。

【输出】

输出从左上角走到右下角至少要经过多少步（即至少要经过多少个空地格子）。计算步数要包括起点和终点。

【输入样例】

5 5
..###
#....
#.#.#
#.#.#
#.#..

【输出样例】

广搜模板题，直接上bfs模板即可

#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
int vis[101][101];

int dx[4] = {1, -1, 0, 0};

int dy[4] = {0, 0, 1, -1};
char a[101][101];
int nx, ny;
int r, c;

struct node {
	int x;
	int y;
	int step = 0;
} b[10001];

void bfs(int x, int y) {
	int h = 1, t = 1;
	b[h].x = x;
	b[h].y = y;
	b[h].step = 1;
	while (h <= t) {
		for (int i = 0; i <= 3; i++) {
			nx = b[h].x + dx[i];
			ny = b[h].y + dy[i];
			if (nx == r && ny == c) {
				cout << b[h].step + 1;
				return;
			} else if (!vis[nx][ny] && nx >= 1 && nx <= r && ny >= 1 && ny <= c && a[nx][ny] == '.') {
				t++;
				b[t].x = nx;
				b[t].y = ny;
				b[t].step = b[h].step + 1;
				vis[nx][ny] = 1;
			}
		}
		h++;
	}
}

int main() {
	cin >> r >> c;
	for (int i = 1; i <= r; i++) {
		for (int j = 1; j <= c; j++) {
			cin >> a[i][j];
		}
	}
	bfs(1, 1);
	return 0;
}