lw

用户名：saudade

访问量：13842

签　名：

等　　级
排　　名	176
经　　验	6864
参赛次数	23
文章发表	25
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

得得得得得
浏览：251

你可能喜欢

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

信息学奥赛一本通T1251-仙岛求药-题解（C++代码）

　　作者: lw　　　　发表时间：2021-01-26 10:17:26 浏览：1352　|　评论：0　

原题链接：信息学奥赛一本通T1251-仙岛求药

#### 闲来无事做的
#### 典型的BFS题目，不需要绕什么弯，解析都在代码注释里
```cpp
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;

// 信息结点 
struct node {
	// x:当前x坐标，y:当前y坐标，s:当前走的距离 
	int x, y, s;
	// 构造器 
	node (int cx, int cy, int cs):x(cx), y(cy), s(cs) {}
};
int m, n;	// 图的大小 
char graph[25][25];	// 图	 
bool vis[25][25];	// 访问数组 
int ans;	// 答案  
int ix, iy;	// 人物初始位置 
queue<node> que;	// bfs所用队列 
// 按 上左下右 四个方向行走时x坐标的变化
int ax[4] = {0, 1, 0, -1};	 
// 按 上左下右 四个方向行走时y坐标的变化
int ay[4] = {1, 0, -1, 0};

void bfs(int x, int y) {
	// 将初始位置存入队列，并置距离为0 
	que.push(node(x, y, 0));
	// 置当前位置已被访问 
	vis[x][y] = 1;
	// 下一步的位置变量 
	int tx, ty;
	// 队列不空就一直广搜 
	while (que.size()) {
		// 取出头结点 
		node tmp = que.front();
		// 弹出头结点 
		que.pop();
		// 向四个方向移动 
		for (int i = 0; i < 4; i++) {
			// 计算位置 
			tx = tmp.x + ax[i];
			ty = tmp.y + ay[i];
			// 位置越界，continue 
			if (tx < 0 || tx >= m || ty < 0 || ty >= n) {
				continue;
			} else if (vis[tx][ty]) {	
			// 已被访问过，continue 
				continue;
			} else if (graph[tx][ty] == '#') {	
			// 此位置是怪物，不可通过，continue 
				continue;
			} else if (graph[tx][ty] == '*') {	
			// 找到仙草，更新ans，并return 
				ans = tmp.s + 1;
				return ;
			} else {	
			// 将当前节点加入队列，距离为上一点位置+1，并置访问数组为1 
				vis[tx][ty] = 1;
				que.push(node(tx, ty, tmp.s + 1));
			}
		}
	}
}

int main() {
	// 优化输入输出 
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	// 多组数据输入 
	while (cin >> m >> n && m && n) {
		// 输入 m * n 的图并存储 
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				cin >> graph[i][j];
				// 人物初始位置 
				if (graph[i][j] == '@') {
					ix = i;
					iy = j;
				}
			}
		}
		// 重置答案
		ans = -1;
		// 清空队列 
		while (que.size()) {
			que.pop();
		}
		// 重置访问数组 
		memset(vis, 0, sizeof(vis));
		// 调用bfs 
		bfs(ix, iy);
		// 输出答案 
		cout << ans << endl;
	}
	return 0;
}
```
*2021-01-26 13:19:36 星期二*

0.0分

7 人评分

新上线《蓝桥杯辅导》课程，近五年的蓝桥杯省赛与国赛真题都有，从读题开始理解题意、梳理思路、实现代码再提交评测全过程，可有效提升获奖比例甚至进国赛！课程介绍、试听请猛击这里

lw

TA的其他文章

你可能喜欢

Hello, world! （C语言代码）

The 3n + 1 problem （C语言代码）

C二级辅导-求偶数和（C语言代码）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

信息学奥赛一本通T1251-仙岛求药-题解（C++代码）

评论区

精彩推荐

【明明的随机数】（C++代码）

人见人爱A+B （C语言代码）

剪刀石头布（C语言代码）不知道怎么直接在scanf中用枚举变量

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题12.2 （C语言代码）

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

1415题求解

lw

TA的其他文章

你可能喜欢

Hello, world! （C语言代码）

The 3n + 1 problem （C语言代码）

C二级辅导-求偶数和 （C语言代码）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

信息学奥赛一本通T1251-仙岛求药-题解（C++代码）

评论区

精彩推荐

【明明的随机数】 （C++代码）

人见人爱A+B （C语言代码）

剪刀石头布 （C语言代码）不知道怎么直接在scanf中用枚举变量

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题12.2 （C语言代码）

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

1415题求解

C二级辅导-求偶数和（C语言代码）

　　评论区

【明明的随机数】（C++代码）

剪刀石头布（C语言代码）不知道怎么直接在scanf中用枚举变量