咖啡


私信TA

用户名:Tianxn

访问量:85966

签 名:

十年OI一场空,不开LL见祖宗。

等  级
排  名 7
经  验 20028
参赛次数 9
文章发表 197
年  龄 22
在职情况 学生
学  校 西安航空学院
专  业 软件工程

  自我简介:

解题思路:
这里就只说一下记录路径的问题吧,既然写到这个题目了,BFS和DFS基本用法都基本掌握了吧。


这里使用一位数组记录路径pre[i]:表示第i个坐标的紧相邻的上一个坐标,倒着来一直到0即可。

那么怎么把坐标存到一维数组里面呢(可以使用二位数组哈),比如坐标(i,j),那么讲5 * i + j存储到数组中就可表示坐标了,到时候取出的时候(x)只要x/5,x%5分别就是横纵坐标呢~
注意事项:

参考代码:

#include <iostream>
#include <queue>
using namespace std;

int a[10][10]; // 迷宫+标记数组 
int pre[30]; // 记录路径 
int nxt[4][2] = {1, 0, -1, 0, 0, 1, 0, -1}; // 辅助数组 

void show(int n) {
	if (!pre[n]) {
		cout << "(0, 0)" << endl;
		return;
	}
	show(pre[n]);
	cout << "(" << pre[n] / 5 << ", " << pre[n] % 5 << ")" << endl;
}

void bfs() {
	queue<pair<int, int> > q;
	q.push(make_pair(0, 0));
	a[0][0] = -1;
	while (!q.empty()) {
		int now_x = q.front().first, now_y = q.front().second;
		for (int i = 0; i < 4; ++i) {
			int new_x = now_x + nxt[i][0], new_y = now_y + nxt[i][1];
			if (new_x < 0 || new_x > 4 || new_y < 0 || new_y > 4) continue;
			if (a[new_x][new_y]) continue;
			pre[5 * new_x + new_y] = 5 * now_x + now_y;
			if (new_x == 4 && new_y == 4) {
				show(24); 
				return;
			}
			q.push(make_pair(new_x, new_y));
			a[new_x][new_y] = -1;
		}
		q.pop();
	}
}
 
int main() {
	for (int i = 0; i < 5; ++i)
		for (int j = 0; j < 5; cin >> a[i][j++]);
	bfs();
	cout << "(4, 4)" << endl;
	return 0;
}


 

0.0分

3 人评分

  评论区

嘎嘎嘎
2021-10-07 14:14:15 | |
  • «
  • 1
  • »