代码随想录算法训练营Day51 | 101.孤岛的总面积、102.沉没孤岛、103.水流问题、104.建造最大岛屿

文章目录

101.孤岛的总面积
- 思路与重点
102.沉没孤岛
- 思路与重点
103.水流问题
- 思路与重点
104.建造最大岛屿
- 思路与重点

101.孤岛的总面积

题目链接：101.孤岛的总面积
讲解链接：代码随想录
状态：直接看题解了。

思路与重点

nextx或者nexty越界了则说明当前的x或y处于边界处，所以当前的岛不是孤岛，不能记入总面积。

#include<iostream>
#include<vector>
using namespace std;
int dir[4][2] = {0, 1, 0, -1, 1, 0 ,-1, 0};
void dfs(int& tempans, bool& flag, const vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y){
    for(int i = 0; i < 4; i++){
        int nextx = x + dir[i][0];
        int nexty = y + dir[i][1];
        if(nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()){
            flag = false;
            continue;
        }
        if(!visited[nextx][nexty] && grid[nextx][nexty] == 1){
            visited[nextx][nexty] = 1;
            tempans++;
            dfs(tempans, flag, grid, visited, nextx, nexty);
        }
    }
}

int main(){
    int ans = 0;
    int n, m;
    cin >> n >> m;
    vector<vector<int>> grid(n, vector<int>(m, 0));
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> grid[i][j];
        }
    }
    vector<vector<bool>> visited(n, vector<bool>(m, false));
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(!visited[i][j] && grid[i][j] == 1){
                visited[i][j] = true;
                bool flag = true;
                int tempans = 1;
                dfs(tempans, flag, grid, visited, i, j);
                if(flag) ans += tempans;
            }
        }
    }    
    cout << ans << endl;
}

也可以将地图边缘的陆地全部变成海洋，再遍历一遍陆地统计面积即可。

#include <iostream>
#include <vector>
using namespace std;
int dir[4][2] = {-1, 0, 0, -1, 1, 0, 0, 1}; // 保存四个方向
int count; // 统计符合题目要求的陆地空格数量
void dfs(vector<vector<int>>& grid, int x, int y) {
    grid[x][y] = 0;
    count++;
    for (int i = 0; i < 4; i++) { // 向四个方向遍历
        int nextx = x + dir[i][0];
        int nexty = y + dir[i][1];
        // 超过边界
        if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;
        // 不符合条件，不继续遍历
        if (grid[nextx][nexty] == 0) continue;

        dfs (grid, nextx, nexty);
    }
    return;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> grid(n, vector<int>(m, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
        }
    }

    // 从左侧边，和右侧边 向中间遍历
    for (int i = 0; i < n; i++) {
        if (grid[i][0] == 1) dfs(grid, i, 0);
        if (grid[i][m - 1] == 1) dfs(grid, i, m - 1);
    }
    // 从上边和下边 向中间遍历
    for (int j = 0; j < m; j++) {
        if (grid[0][j] == 1) dfs(grid, 0, j);
        if (grid[n - 1][j] == 1) dfs(grid, n - 1, j);
    }
    count = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == 1) dfs(grid, i, j);
        }
    }
    cout << count << endl;
}

102.沉没孤岛

题目链接：102.沉没孤岛
讲解链接：代码随想录
状态：一遍AC。

思路与重点

先找到孤岛进行标记，然后再DFS把孤岛全部沉没。

#include<iostream>
#include<vector>
using namespace std;
int dir[4][2] = {0, 1, 0, -1, 1, 0 ,-1, 0};
void dfs(bool& flag, vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y){
    for(int i = 0; i < 4; i++){
        int nextx = x + dir[i][0];
        int nexty = y + dir[i][1];
        if(nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()){
            flag = false;
            continue;
        }
        if(!visited[nextx][nexty] && grid[nextx][nexty] == 1){
            visited[nextx][nexty] = 1;
            dfs(flag, grid, visited, nextx, nexty);
        }
    }
}

void isoDfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y){
    for(int i = 0; i < 4; i++){
        int nextx = x + dir[i][0];
        int nexty = y + dir[i][1];
        if(nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()){
            continue;
        }
        if(!visited[nextx][nexty] && grid[nextx][nexty] == 1){
            visited[nextx][nexty] = 1;
            grid[nextx][nexty] = 0;
            isoDfs(grid, visited, nextx, nexty);
        }
    }
}

int main(){
    int n, m;
    cin >> n >> m;
    vector<vector<int>> grid(n, vector<int>(m, 0));
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> grid[i][j];
        }
    }
    vector<vector<bool>> visited(n, vector<bool>(m, false));
    vector<pair<int, int>> isoland;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(!visited[i][j] && grid[i][j] == 1){
                visited[i][j] = true;
                bool flag = true;
                dfs(flag, grid, visited, i, j);
                if(flag) isoland.push_back(make_pair(i,j));
            }
        }
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            visited[i][j] = false;
        }
    }
    for(auto tempPair : isoland){
        grid[tempPair.first][tempPair.second] = 0;
        isoDfs(grid, visited, tempPair.first, tempPair.second);
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(j == 0) cout << grid[i][j];
            else cout << ' ' << grid[i][j];
        }
        cout << endl;
    }
}

不用额外定义空间了，标记周边的陆地，可以直接改陆地为其他特殊值作为标记。步骤一：深搜或者广搜将地图周边的 1 （陆地）全部改成 2 （特殊标记）；步骤二：将水域中间 1 （陆地）全部改成水域（0）；步骤三：将之前标记的 2 改为 1 （陆地）

#include <iostream>
#include <vector>
using namespace std;
int dir[4][2] = {-1, 0, 0, -1, 1, 0, 0, 1}; // 保存四个方向
void dfs(vector<vector<int>>& grid, int x, int y) {
    grid[x][y] = 2;
    for (int i = 0; i < 4; i++) { // 向四个方向遍历
        int nextx = x + dir[i][0];
        int nexty = y + dir[i][1];
        // 超过边界
        if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;
        // 不符合条件，不继续遍历
        if (grid[nextx][nexty] == 0 || grid[nextx][nexty] == 2) continue;
        dfs (grid, nextx, nexty);
    }
    return;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> grid(n, vector<int>(m, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
        }
    }

    // 步骤一：
    // 从左侧边，和右侧边 向中间遍历
    for (int i = 0; i < n; i++) {
        if (grid[i][0] == 1) dfs(grid, i, 0);
        if (grid[i][m - 1] == 1) dfs(grid, i, m - 1);
    }

    // 从上边和下边 向中间遍历
    for (int j = 0; j < m; j++) {
        if (grid[0][j] == 1) dfs(grid, 0, j);
        if (grid[n - 1][j] == 1) dfs(grid, n - 1, j);
    }
    // 步骤二、步骤三
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == 1) grid[i][j] = 0;
            if (grid[i][j] == 2) grid[i][j] = 1;
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cout << grid[i][j] << " ";
        }
        cout << endl;
    }
}

103.水流问题

题目链接：103.水流问题
讲解链接：代码随想录
状态：自己写了会儿再看题解。

思路与重点

我自己的代码过不了test5和test7，也没找出问题在哪儿，等二刷的时候再看看。
感觉是**到达左边界和上边界的方法会包含先往右走再往上走，**不能直接把dir分成两组来做。
还是会超时，直接看题解吧。

#include<iostream>
#include<vector>
using namespace std;
int dir[2][2][2] = {-1, 0, 0, -1, 1, 0, 0, 1};
bool dfs(const vector<vector<int>>& grid, vector<vector<bool>>& ans, int x, int y, int dirIdx){
    for(int i = 0; i < 2; i++){
        int nextx = x + dir[dirIdx][i][0];
        int nexty = y + dir[dirIdx][i][1];
        if(nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()){
            return true;
        }
        if(grid[nextx][nexty] <= grid[x][y]){
            if(ans[nextx][nexty]) return true;
            if(dfs(grid, ans, nextx, nexty, dirIdx)) return true;
        }
    }
    return false;
}

int main(){
    int n, m;
    cin >> n >> m;
    vector<vector<int>> grid(n, vector<int>(m, 0));
    vector<vector<bool>> ans(n, vector<bool>(m, false));
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> grid[i][j];
        }
    }
    ans[n-1][0] = true;
    ans[0][m-1] = true;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(ans[i][j] == false){
                bool flag1 = dfs(grid, ans, i, j, 0);
                bool flag2 = dfs(grid, ans, i, j, 1);
                if(flag1 && flag2){
                    ans[i][j] = true;
                }
            }
        }        
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(ans[i][j] == true){
                cout << i << ' ' << j << endl;
            }
        }        
    }
    return 0;
}

我们可以反过来想，从第一组边界上的节点逆流而上，将遍历过的节点都标记上。同样从第二组边界的边上节点逆流而上，将遍历过的节点也标记上。然后两方都标记过的节点就是既可以流太平洋也可以流大西洋的节点。

#include <iostream>
#include <vector>
using namespace std;
int n, m;
int dir[4][2] = {-1, 0, 0, -1, 1, 0, 0, 1};
void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y) {
    if (visited[x][y]) return;

    visited[x][y] = true;

    for (int i = 0; i < 4; i++) {
        int nextx = x + dir[i][0];
        int nexty = y + dir[i][1];
        if (nextx < 0 || nextx >= n || nexty < 0 || nexty >= m) continue;
        if (grid[x][y] > grid[nextx][nexty]) continue; // 注意：这里是从低向高遍历

        dfs (grid, visited, nextx, nexty);
    }
    return;
}



int main() {

    cin >> n >> m;
    vector<vector<int>> grid(n, vector<int>(m, 0));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
        }
    }
    // 标记从第一组边界上的节点出发，可以遍历的节点
    vector<vector<bool>> firstBorder(n, vector<bool>(m, false));

    // 标记从第一组边界上的节点出发，可以遍历的节点
    vector<vector<bool>> secondBorder(n, vector<bool>(m, false));

    // 从最上和最下行的节点出发，向高处遍历
    for (int i = 0; i < n; i++) {
        dfs (grid, firstBorder, i, 0); // 遍历最左列，接触第一组边界
        dfs (grid, secondBorder, i, m - 1); // 遍历最右列，接触第二组边界
    }

    // 从最左和最右列的节点出发，向高处遍历
    for (int j = 0; j < m; j++) {
        dfs (grid, firstBorder, 0, j); // 遍历最上行，接触第一组边界
        dfs (grid, secondBorder, n - 1, j); // 遍历最下行，接触第二组边界
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            // 如果这个节点，从第一组边界和第二组边界出发都遍历过，就是结果
            if (firstBorder[i][j] && secondBorder[i][j]) cout << i << " " << j << endl;;
        }
    }


}

104.建造最大岛屿

题目链接：104.建造最大岛屿
讲解链接：代码随想录
状态：暴力解法直接AC了。

思路与重点

依次将所有海洋变成陆地，然后从变化的陆地出发找当前岛屿最大面积，注意没有海洋的特殊情况。

#include <iostream>
#include <vector>
using namespace std;
int ans = 1;
int n, m;
int dir[4][2] = {-1, 0, 0, -1, 1, 0, 0, 1};
void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y, int& tempans) {
    if (visited[x][y]) return;
    visited[x][y] = true;
    tempans++;
    for (int i = 0; i < 4; i++) {
        int nextx = x + dir[i][0];
        int nexty = y + dir[i][1];
        if (nextx < 0 || nextx >= n || nexty < 0 || nexty >= m) continue;
        if (grid[nextx][nexty] == 0) continue; // 注意：这里是从低向高遍历
        dfs (grid, visited, nextx, nexty, tempans);
    }
    return;
}



int main() {

    cin >> n >> m;
    vector<vector<int>> grid(n, vector<int>(m, 0));
    bool changeFlag = false;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
        }
    }
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if(grid[i][j] == 0){
                changeFlag = true;
                vector<vector<bool>> visited(n, vector<bool>(m, false));
                int tempans = 0;
                grid[i][j] = 1;
                dfs(grid, visited, i, j, tempans);
                ans = ans > tempans ? ans : tempans;
                grid[i][j] = 0;
            }
        }
    }    
    if(changeFlag) cout << ans << endl;
    else cout << n * m << endl;
    
    return 0;
}

其实每次深搜遍历计算最大岛屿面积，我们都做了很多重复的工作。只要用一次深搜把每个岛屿的面积记录下来就好。
- 第一步：一次遍历地图，得出各个岛屿的面积，并做编号记录。可以使用map记录，key为岛屿编号，value为岛屿面积
- 第二步：再遍历地图，遍历0的方格（因为要将0变成1），并统计该1（由0变成的1）周边岛屿面积，将其相邻面积相加在一起，遍历所有 0 之后，就可以得出选一个0变成1 之后的最大面积。

#include <iostream>
#include <vector>
#include <unordered_set>
#include <unordered_map>
using namespace std;
int n, m;
int count;

int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 四个方向
void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y, int mark) {
    if (visited[x][y] || grid[x][y] == 0) return; // 终止条件：访问过的节点 或者 遇到海水
    visited[x][y] = true; // 标记访问过
    grid[x][y] = mark; // 给陆地标记新标签
    count++;
    for (int i = 0; i < 4; i++) {
        int nextx = x + dir[i][0];
        int nexty = y + dir[i][1];
        if (nextx < 0 || nextx >= n || nexty < 0 || nexty >= m) continue;  // 越界了，直接跳过
        dfs(grid, visited, nextx, nexty, mark);
    }
}

int main() {
    cin >> n >> m;
    vector<vector<int>> grid(n, vector<int>(m, 0));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
        }
    }
    vector<vector<bool>> visited(n, vector<bool>(m, false)); // 标记访问过的点
    unordered_map<int ,int> gridNum;
    int mark = 2; // 记录每个岛屿的编号
    bool isAllGrid = true; // 标记是否整个地图都是陆地
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == 0) isAllGrid = false;
            if (!visited[i][j] && grid[i][j] == 1) {
                count = 0;
                dfs(grid, visited, i, j, mark); // 将与其链接的陆地都标记上 true
                gridNum[mark] = count; // 记录每一个岛屿的面积
                mark++; // 记录下一个岛屿编号
            }
        }
    }
    if (isAllGrid) {
        cout << n * m << endl; // 如果都是陆地，返回全面积
        return 0; // 结束程序
    }

    // 以下逻辑是根据添加陆地的位置，计算周边岛屿面积之和
    int result = 0; // 记录最后结果
    unordered_set<int> visitedGrid; // 标记访问过的岛屿
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            count = 1; // 记录连接之后的岛屿数量
            visitedGrid.clear(); // 每次使用时，清空
            if (grid[i][j] == 0) {
                for (int k = 0; k < 4; k++) {
                    int neari = i + dir[k][1]; // 计算相邻坐标
                    int nearj = j + dir[k][0];
                    if (neari < 0 || neari >= n || nearj < 0 || nearj >= m) continue;
                    if (visitedGrid.count(grid[neari][nearj])) continue; // 添加过的岛屿不要重复添加
                    // 把相邻四面的岛屿数量加起来
                    count += gridNum[grid[neari][nearj]];
                    visitedGrid.insert(grid[neari][nearj]); // 标记该岛屿已经添加过
                }
            }
            result = max(result, count);
        }
    }
    cout << result << endl;

}