lw

用户名：saudade

访问量：12528

签　名：

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

　　自我简介：

TA的其他文章

Jam的计数法-题解（C++代码）
浏览：360

数据结构-Floyd(弗洛伊德)最短路径算法-题解（C++代码）
浏览：256

数据结构-有向无环图的拓扑排序-题解（C语言代码）
浏览：540

你可能喜欢

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

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

　　作者: lw　　　　发表时间：2021-01-26 10:17:26 浏览：1108　|　评论：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 人评分

C语言网推出会员服务，提供C/C++/算法/Python等多套视频学练课程+源码资源社群答疑+私活推荐等资源，享受丰富的技术学习到变现的乐趣，以含金量和学习效果勇敢挑战同类辅导！点击了解开通

lw

TA的其他文章

你可能喜欢

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

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

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

IP判断（C语言代码）

C语言训练-求PI* （C语言代码）

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

评论区

精彩推荐

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

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

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

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

母牛的故事（C语言代码）

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

愚蠢的摄影师（C++代码）

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

A+B for Input-Output Practice （C语言代码）

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

lw

TA的其他文章

你可能喜欢

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

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

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

IP判断 （C语言代码）

C语言训练-求PI* （C语言代码）

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

评论区

精彩推荐

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

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 （C语言代码）

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

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

母牛的故事 （C语言代码）

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

愚蠢的摄影师 （C++代码）

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

A+B for Input-Output Practice （C语言代码）

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

IP判断（C语言代码）

　　评论区

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

母牛的故事（C语言代码）

愚蠢的摄影师（C++代码）