PAT题解 --- 寻宝图
今天是PTA题库解法讲解的第十天，今天我们要讲解浪漫侧影，题目如下：
题解思路：
要解决这个问题，可以使用深度优先搜索（DFS）方法来遍历每一个陆地或宝藏格子，标记所有与之相连的格子，从而识别出一个岛屿。遇到未访问过的陆地或宝藏格子时，就开始一个新的DFS过程。如果在岛屿中发现有宝藏（值为2-9的格子），则此岛屿为有宝藏的岛屿。这种方法能高效地遍历地图，将格子分组成岛屿，并识别出含宝藏的岛屿。
C语言实现：
#include <stdio.h>
#define MAXN 105
int n, m;
int grid[MAXN][MAXN];
int visited[MAXN][MAXN];
void dfs(int x, int y, int* hasTreasure) {
if(x < 0 || x >= n || y < 0 || y >= m || visited[x][y] || grid[x][y] == 0) return;
visited[x][y] = 1;
if(grid[x][y] >= 2 && grid[x][y] <= 9) *hasTreasure = 1;
dfs(x+1, y, hasTreasure); // down
dfs(x-1, y, hasTreasure); // up
dfs(x, y+1, hasTreasure); // right
dfs(x, y-1, hasTreasure); // left
}
int main() {
// Assume input has been read into `grid`
// Initialize `visited` to 0
int islands = 0, treasureIslands = 0;
for(int i = 0; i < n; ++i) {
for(int j = 0; j < m; ++j) {
if(!visited[i][j] && grid[i][j] != 0) {
int hasTreasure = 0;
dfs(i, j, &hasTreasure);
islands++;
treasureIslands += hasTreasure;
}
}
}
printf("%d %d\n", islands, treasureIslands);
return 0;
}本文参与?腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2024-03-23，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读