AcWing 5015. 寻宝图
原题链接
中等
作者:
jx-dzpc
,
2024-02-16 12:13:40
,
所有人可见
,
阅读 132
chatGPT4.0写的😅
寻宝图
#include <iostream>
#include <vector>
using namespace std;
int N, M;
vector<vector<int>> grid;
vector<vector<bool>> visited;
// DFS来遍历岛屿
bool dfs(int x, int y) {
if (x < 0 || x >= N || y < 0 || y >= M || grid[x][y] == 0 || visited[x][y]) {
// 越界或者是水域,或者已经访问过
return false;
}
visited[x][y] = true; // 标记当前格子已访问
bool hasTreasure = grid[x][y] > 1; // 检查当前岛屿是否含有宝藏
// 遍历四个方向的相邻格子
hasTreasure |= dfs(x + 1, y);
hasTreasure |= dfs(x - 1, y);
hasTreasure |= dfs(x, y + 1);
hasTreasure |= dfs(x, y - 1);
return hasTreasure;
}
int main() {
cin >> N >> M;
grid = vector<vector<int>>(N, vector<int>(M));
visited = vector<vector<bool>>(N, vector<bool>(M, false));
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) {
char ch;
cin >> ch;
grid[i][j] = ch - '0';
}
}
int totalIslands = 0, treasureIslands = 0;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) {
if (grid[i][j] != 0 && !visited[i][j]) { // 找到一个未访问的陆地格子
if (dfs(i, j)) { // 如果dfs返回true,则当前岛屿含有宝藏
treasureIslands++;
}
totalIslands++; // 每次dfs搜索完成后,岛屿总数加1
}
}
}
cout << totalIslands << " " << treasureIslands << endl;
return 0;
}
这种还挺板的题gpt还是比较容易写的~~~,换一些思维题就不太行了
的确,但想想也可怕 未来会进化成什么样?🤦♂️