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

时间：2024-07-06 06:59:54

101.孤岛的总面积

题目链接：https://kamacoder.com/problempage.php?pid=1173
文档讲解：https://programmercarl.com/kamacoder/0101.%E5%AD%A4%E5%B2%9B%E7%9A%84%E6%80%BB%E9%9D%A2%E7…

思路

本题要求找到不靠边的陆地面积，那么我们只要从周边找到陆地然后 通过 dfs或者bfs 将周边靠陆地且相邻的陆地都变成海洋，然后再去重新遍历地图 统计此时还剩下的陆地就可以了。

代码

import java.util.*;

class Main {
    static int[][] grid;
    static int count = 0;
    static int[][] dir = {{1, 0}, {0, 1}, {0, -1}, {-1, 0}};
    public static void main (String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), m = in.nextInt();
        grid = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                grid[i][j] = in.nextInt();
            }
        }
        
        for (int i = 0; i < n; i++) { // 从第一列和最后一列向中间遍历
            if (grid[i][0] == 1) bfs(i, 0);
            if (grid[i][m - 1] == 1) bfs(i, m - 1);
        }
        for (int i = 0; i < m; i++) { //从第一行和最后一行向中间遍历
            if (grid[0][i] == 1) bfs(0, i);
            if (grid[n - 1][i] == 1) bfs(n - 1, i);
        }
        count = 0; // 清空之前记录的陆地数
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) {
                    bfs(i, j);
                }
            } 
        }
        System.out.println(count);
    }
    
    public static void bfs(int x, int y) {
        count++;
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{x, y});
        grid[x][y] = 0;
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int curX = cur[0], curY = cur[1];
            for (int i = 0; i < 4; i++) {
                int nextX = curX + dir[i][0], nextY = curY + dir[i][1];
                if (nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length) continue;
                if (grid[nextX][nextY] == 1) {
                    queue.offer(new int[]{nextX, nextY});
                    grid[nextX][nextY] = 0;
                    count++;
                }
            }
        }
        
    }
    
    public static void dfs(int x, int y) {
        grid[x][y] = 0; // 将与边界相连的陆地变为水
        count++; // 统计陆地数量
        for (int i = 0; i < 4; i++) {
            int nextX = x + dir[i][0], nextY = y + dir[i][1];
            if (nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length) continue;
            if (grid[nextX][nextY] == 1) dfs(nextX, nextY);
        }
    }
}

这道题在卡码网上提交java的dfs和bfs都会超时，但是思路是和C++一样的。

102.沉没孤岛

题目链接：https://kamacoder.com/problempage.php?pid=1174
文档讲解：https://programmercarl.com/kamacoder/0102.%E6%B2%89%E6%B2%A1%E5%AD%A4%E5%B2%9B.html

思路

第一步：深搜或者广搜将地图周边的 1 （陆地）全部改成 2 （特殊标记）
第二步：将水域中间 1 （陆地）全部改成 水域（0）
第三步：将之前标记的 2 改为 1 （陆地）

代码

import java.util.*;

class Main{
    static int[][] grid;
    static int[][] dir = {{1, 0}, {0, 1}, {0, -1}, {-1, 0}};
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), m = in.nextInt();
        grid = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                grid[i][j] = in.nextInt();
            }
        }
        
        for (int i = 0; i < n; i++) {
            if (grid[i][0] == 1) bfs(i, 0);
            if (grid[i][m - 1] == 1) bfs(i, m - 1);
        }
        for (int i = 0; i < m; i++) {
            if (grid[0][i] == 1) bfs(0, i);
            if (grid[n - 1][i] == 1) bfs(n - 1, i);
        }
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) grid[i][j] = 0;
                else if (grid[i][j] == 2) grid[i][j] = 1;
                System.out.print(grid[i][j] + " ");
            }
            System.out.println();
        }
    }
    
    public static void bfs(int x, int y) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{x, y});
        grid[x][y] = 2;
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int curX = cur[0], curY = cur[1];
            for (int i = 0; i < 4; i++) {
                int nextX = curX + dir[i][0], nextY = curY + dir[i][1];
                if (nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length) continue;
                if (grid[nextX][nextY] == 1) {
                    grid[nextX][nextY] = 2;
                    queue.offer(new int[]{nextX, nextY});
                }
            }
        }
    }
    
    public static void dfs(int x, int y) {
        grid[x][y] = 2;
        for (int i = 0; i < 4; i++) {
            int nextX = x + dir[i][0], nextY = y + dir[i][1];
            if (nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length) continue;
            if (grid[nextX][nextY] == 1) dfs(nextX, nextY);
        }
    }
}

103.水流问题

题目链接：https://kamacoder.com/problempage.php?pid=1175
文档讲解：https://programmercarl.com/kamacoder/0103.%E6%B0%B4%E6%B5%81%E9%97%AE%E9%A2%98.html

思路

从第一组边界上的节点 逆流而上，将遍历过的节点都标记上。同样从第二组边界的边上节点 逆流而上，将遍历过的节点也标记上。然后两方都标记过的节点就是既可以流第一边界也可以流第二边界的节点。

代码

import java.util.*;

class Main {
    static int[][] grid;
    static int[][] dir = {{1, 0}, {0, 1}, {0, -1}, {-1, 0}};
    
    public static void main (String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), m = in.nextInt();
        grid = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                grid[i][j] = in.nextInt();
            }
        }
        boolean[][] visited1 = new boolean[n][m];
        boolean[][] visited2 = new boolean[n][m];
        for (int i = 0; i < n; i++) {
            bfs(visited1, i, 0); // 最左列，为第一组
            bfs(visited2, i, m - 1); // 最右列，为第二组
        }
        for (int i = 0; i < m; i++) {
            bfs(visited1, 0, i); // 第一行，为第一组
            bfs(visited2, n - 1, i); // 第二行，为第二组
        }
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (visited1[i][j] && visited2[i][j]) {
                    System.out.println(i + " " + j);
                }
            }
        }
    }
    
    public static void bfs(boolean[][] visited, int x, int y) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{x, y});
        visited[x][y] = true;
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int curX = cur[0], curY = cur[1];
            for (int i = 0; i < 4; i++) {
                int nextX = curX + dir[i][0], nextY = curY + dir[i][1];
                if (nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length) continue;
                if (!visited[nextX][nextY] && grid[curX][curY] <= grid[nextX][nextY]) {
                    queue.offer(new int[]{nextX, nextY});
                    visited[nextX][nextY] = true;
                }
            }
        }
    }
    
    public static void dfs(boolean[][] visited, int x, int y) {
        visited

相关文章