请按以下要求写一段c语言代码:描述 乔瑟夫是个习惯旅游的人,今天他买了地图打算在Z市旅游,Z市有 n个旅游景点,按从 1 到 n 编号。地图中有一组n维矩阵,表示i和j两个景点之间的路程距离。乔瑟夫喜欢自驾游,但是他身上有个魔咒,开车距离大于一定数值d,车子就会爆炸。 如果从景点i出发,到达某一其他景点j的最小开车距离不超过(即小于等于)距离d,则认为景点i存在一个安全景点。 乔瑟夫希望能在地图上找到一个景点,它的安全景点最多,如果有多个安全景点并列最多,则选择编号最大的景点。 输入 输入的第一行是两个整数n(1 ≤ n ≤ 200),表示景点个数;和 d 表示开车不超过的最大距离,d的取值保证一定有符合条件的景点。 接下来是n行,每行n个整数,表示地图中1~n个景点之间的距离w(-1 ≤ w ≤ 100)(0表示景点到自己的距离;-1表示景点i和j之间没有直接路径),景点i到j的距离等于景点j到i的距离。 输出 输出为一个整数,表示符合条件的景点的编号(如果有多个安全景点最多的景点,选择编号最大的景点)。
时间: 2024-02-09 15:11:38 浏览: 128
以下是C语言代码实现:
```c
#include <stdio.h>
#define MAXN 210
#define INF 0x3f3f3f3f
int n, d, map[MAXN][MAXN];
int bfs(int x) { // 以x为起点进行BFS搜索
int queue[MAXN], head = 0, tail = 0;
int visited[MAXN] = {0};
int cnt = 0, ans = x;
queue[tail++] = x;
visited[x] = 1;
while (head < tail) {
int cur = queue[head++];
for (int i = 1; i <= n; i++) {
if (map[cur][i] != -1 && map[cur][i] <= d && !visited[i]) {
queue[tail++] = i;
visited[i] = 1;
cnt++;
if (i > ans) ans = i; // 更新编号最大的安全景点
}
}
}
return cnt;
}
int main() {
scanf("%d %d", &n, &d);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
scanf("%d", &map[i][j]);
if (map[i][j] == -1) map[i][j] = INF; // 把无法到达的点的距离设为INF
}
}
int max_cnt = -1, ans = 0;
for (int i = n; i >= 1; i--) { // 从编号大的景点开始搜索
int cnt = bfs(i);
if (cnt > max_cnt) {
max_cnt = cnt;
ans = i;
}
}
printf("%d\n", ans);
return 0;
}
```
思路解析:
题目要求找到一个安全景点,使得以该景点为起点,到其他景点的最小距离不超过d的景点数最多。因此,我们可以从编号大的景点开始,以该景点为起点进行BFS搜索,找到所有距离小于等于d的景点,并以此更新安全景点的数量和编号最大的安全景点。最后输出满足条件的景点编号即可。
需要注意的是,题目中的距离可能为-1,表示两个景点之间没有直接路径。我们可以把这种情况视为距离为无穷大,即INF,这样在后续的搜索中就不会被考虑到。
阅读全文