代碼隨想錄算法訓(xùn)練營(yíng)第52天 | 圖論part03：101.? 孤島的總面積、102.? 沉沒(méi)孤島、103.? 水流問(wèn)題、104.建造最大島嶼

第十一章：圖論part03

101. 孤島的總面積

基礎(chǔ)題目 可以自己嘗試做一做 。
文章講解

思路

  • 注意孤島的定義是單元格不接觸邊緣。
  • 本題要求找到不靠邊的陸地面積，那么我們只要從周邊找到陸地然后 通過(guò) dfs或者bfs 將周邊靠陸地且相鄰的陸地都變成海洋，然后再去重新遍歷地圖 統(tǒng)計(jì)此時(shí)還剩下的陸地就可以了。
DFS
import java.util.*;

public class Main{
    static int count;
    static int[][] dir = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}}; //下左上右
    
    public static void dfs(int[][] grid, int x, int y){
        grid[x][y] = 0; // 將當(dāng)前格子標(biāo)記為已訪問(wèn)  這里不需要單獨(dú)的visited數(shù)組
        count++; // 增加島嶼面積計(jì)數(shù)
        
        // 向四個(gè)方向遍歷
        for(int i = 0; i < 4; i++){
            int nextx = x + dir[i][0];
            int nexty = y + dir[i][1];
            
            // 檢查下一個(gè)坐標(biāo)是否越界
            if(nextx < 0 || nextx >= grid.length || nexty < 0 || nexty >=grid[0].length) continue;
            
            // 如果下一個(gè)坐標(biāo)是陸地，繼續(xù) DFS
            if(grid[nextx][nexty] == 1) dfs(grid, nextx, nexty);
        }
        
    }
    
    public static void main(String[] args){
        // 初始化網(wǎng)格
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][] grid = new int[n][m];
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                grid[i][j] = sc.nextInt();
            }
        }
        
        // 逐行處理左側(cè)和右側(cè)邊界，所以列是固定的
        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);
        }
        
        // 重置計(jì)數(shù)器
        count = 0;
        
        // 遍歷整個(gè)網(wǎng)格，統(tǒng)計(jì)所有符合條件的陸地空格數(shù)量
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(grid[i][j] == 1) dfs(grid, i, j);
            }
        }
        System.out.println(count);
    }
}
BFS
import java.util.*;

public class Main{
    static int count;
    static int[][] dir = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}}; //下左上右
    
    public static void bfs(int[][] grid, int x, int y){
        // 初始化
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{x, y});
        grid[x][y] = 0; // 標(biāo)記初始坐標(biāo)已訪問(wèn)
        count++;
        
        // 當(dāng)隊(duì)列不為空時(shí)，持續(xù)處理
        while(!queue.isEmpty()){
            int[] current = queue.poll();// 獲取并移除隊(duì)列頭部的元素
            int curx = current[0];// 當(dāng)前處理的 x 坐標(biāo)
            int cury = current[1];// 當(dāng)前處理的 y 坐標(biāo)
            
            // 遍歷四個(gè)方向
            for(int i = 0; i < 4; i++){
                int nextx = curx + dir[i][0];
                int nexty = cury + dir[i][1];
                
                // 檢查下一個(gè)坐標(biāo)是否越界
                if(nextx < 0 || nextx >= grid.length || nexty < 0 || nexty >= grid[0].length) continue;
                if(grid[nextx][nexty] == 1){
                    queue.offer(new int[]{nextx,nexty});
                    count++;
                    grid[nextx][nexty] = 0; // 標(biāo)記為已訪問(wèn)
                }
            }
        }
        
        
    }
    
    public static void main(String[] args){
        // 初始化網(wǎng)格
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][] grid = new int[n][m];
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                grid[i][j] = sc.nextInt();
            }
        }
        
        // 逐行處理左側(cè)和右側(cè)邊界，所以列是固定的
        for(int i = 0; i < n; i++){
            if(grid[i][0] == 1) bfs(grid, i, 0);
            if(grid[i][m - 1] == 1) bfs(grid, i, m - 1);
            
        }
        
        // 處理上下邊界，所以行是固定的
        for(int j = 0; j < m; j++){
            if(grid[0][j] == 1) bfs(grid, 0, j);
            if(grid[n - 1][j] == 1) bfs(grid, n - 1, j);
        }
        
        // 重置計(jì)數(shù)器
        count = 0;
        
        // 遍歷整個(gè)網(wǎng)格，統(tǒng)計(jì)所有符合條件的陸地空格數(shù)量
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(grid[i][j] == 1) bfs(grid, i, j);
            }
        }
        System.out.println(count);
    }
}

102. 沉沒(méi)孤島

和上一題差不多，嘗試自己做做
文章講解

思路

  • 依然是從地圖周邊出發(fā)，將周邊空格相鄰的陸地都做上標(biāo)記，然后在遍歷一遍地圖，遇到 陸地 且沒(méi)做過(guò)標(biāo)記的，那么都是地圖中間的 陸地 ，全部改成水域就行。
    步驟一：深搜或者廣搜將地圖周邊的 1 （陸地）全部改成 2 （特殊標(biāo)記）
    步驟二：將水域中間 1 （陸地）全部改成 水域（0）
    步驟三：將之前標(biāo)記的 2 改為 1 （陸地）
import java.util.*;

public class Main{
    static int[][] dir = {{0,1},{1,0},{0,-1},{-1,0}};
    
    public static void dfs(int[][] grid, int x, int y){
        grid[x][y] = 2;// 標(biāo)記當(dāng)前格子為已訪問(wèn)
        
        // 向四個(gè)方向遍歷
        for(int i = 0; i < 4; i++){
            int nextx = x + dir[i][0];
            int nexty = y + dir[i][1];
            // 檢查下一個(gè)坐標(biāo)是否越界
            if(nextx < 0 || nextx >= grid.length || nexty < 0 || nexty >= grid[0].length) continue;
            // 如果下一個(gè)坐標(biāo)不符合條件，繼續(xù)下一個(gè)方向
            if(grid[nextx][nexty] == 0 || grid[nextx][nexty] == 2) continue;
            
            dfs(grid, nextx, nexty);
        }
        
    }
    
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][] grid = new int[n][m];
        
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                grid[i][j] = sc.nextInt();
            }
        }
        
        // 步驟一：
        // 處理左右側(cè)邊
        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);
        }
        
        // 處理上下側(cè)邊
        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;
            }
        }
        
        // 輸出結(jié)果
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                System.out.print(grid[i][j] + " ");
            }
            System.out.println();
        } 
    }
}

103. 水流問(wèn)題

需要點(diǎn)優(yōu)化思路，建議先自己讀題，想出一個(gè)解題方法，有時(shí)間就自己寫(xiě)代碼，沒(méi)時(shí)間就直接看題解，優(yōu)化方式 會(huì)讓你 耳目一新。
文章講解

思路

從第一組邊界上的節(jié)點(diǎn) 逆流而上，將遍歷過(guò)的節(jié)點(diǎn)都標(biāo)記上。


image.png

同樣從第二組邊界的邊上節(jié)點(diǎn) 逆流而上，將遍歷過(guò)的節(jié)點(diǎn)也標(biāo)記上。


image.png

然后兩方都標(biāo)記過(guò)的節(jié)點(diǎn)就是既可以流太平洋也可以流大西洋的節(jié)點(diǎn)。

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    static int n, m;
    static int[][] dir = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}}; // 保存四個(gè)方向

    // 深度優(yōu)先搜索 (DFS) 方法
    public static void dfs(int[][] grid, boolean[][] visited, int x, int y) {
        if (visited[x][y]) return; // 如果已經(jīng)訪問(wèn)過(guò)，直接返回

        visited[x][y] = true; // 標(biāo)記為已訪問(wèn)

        // 向四個(gè)方向遍歷
        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); // 遞歸調(diào)用 DFS
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        int[][] grid = new int[n][m];

        // 讀取網(wǎng)格數(shù)據(jù)
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                grid[i][j] = sc.nextInt();
            }
        }

        // 標(biāo)記從第一組邊界上的節(jié)點(diǎn)出發(fā)，可以遍歷的節(jié)點(diǎn)
        boolean[][] firstBorder = new boolean[n][m];

        // 標(biāo)記從第二組邊界上的節(jié)點(diǎn)出發(fā)，可以遍歷的節(jié)點(diǎn)
        boolean[][] secondBorder = new boolean[n][m];

        // 從最左和最右列的節(jié)點(diǎn)出發(fā)，向高處遍歷
        for (int i = 0; i < n; i++) {
            dfs(grid, firstBorder, i, 0); // 遍歷最左列，接觸第一組邊界
            dfs(grid, secondBorder, i, m - 1); // 遍歷最右列，接觸第二組邊界
        }

        // 從最上和最下行的節(jié)點(diǎn)出發(fā)，向高處遍歷
        for (int j = 0; j < m; j++) {
            dfs(grid, firstBorder, 0, j); // 遍歷最上行，接觸第一組邊界
            dfs(grid, secondBorder, n - 1, j); // 遍歷最下行，接觸第二組邊界
        }

        // 輸出結(jié)果
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // 如果這個(gè)節(jié)點(diǎn)，從第一組邊界和第二組邊界出發(fā)都遍歷過(guò)，就是結(jié)果
                if (firstBorder[i][j] && secondBorder[i][j]) {
                    System.out.println(i + " " + j);
                }
            }
        }
    }
}

本題整體的時(shí)間復(fù)雜度其實(shí)是： 2 * n * m + n * m ，所以最終時(shí)間復(fù)雜度為 O(n * m) ?？臻g復(fù)雜度為：O(n * m) 這個(gè)就不難理解了。開(kāi)了幾個(gè) n * m 的數(shù)組。
時(shí)間復(fù)雜度怎么算的暫時(shí)沒(méi)整明白，二刷記得看。

104.建造最大島嶼

同樣優(yōu)化思路也會(huì)讓你耳目一新，自己想比較難想出來(lái)。
文章講解

思路

暴力解法：

應(yīng)該是遍歷地圖嘗試 將每一個(gè) 0 改成1，然后去搜索地圖中的最大的島嶼面積。
計(jì)算地圖的最大面積：遍歷地圖 + 深搜島嶼，時(shí)間復(fù)雜度為 n * n。
每改變一個(gè)0的方格，都需要重新計(jì)算一個(gè)地圖的最大面積，所以 整體時(shí)間復(fù)雜度為：n^4。

優(yōu)化思路：

只要用一次深搜把每個(gè)島嶼的面積記錄下來(lái)就好。

  • 第一步：一次遍歷地圖，得出各個(gè)島嶼的面積，并做編號(hào)記錄。可以使用map記錄，key為島嶼編號(hào)，value為島嶼面積

  • 第二步：再遍歷地圖，遍歷0的方格（因?yàn)橐獙?變成1），并統(tǒng)計(jì)該1（由0變成的1）周邊島嶼面積，將其相鄰面積相加在一起，遍歷所有 0 之后，就可以得出 選一個(gè)0變成1 之后的最大面積。

拿如下地圖的島嶼情況來(lái)舉例： （1為陸地）
image.png

第一步，則遍歷題目，并將島嶼到編號(hào)和面積上的統(tǒng)計(jì)，過(guò)程如圖所示：
image.png

代碼如下

    static int count;
    static int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}}; // 四個(gè)方向

    public void dfs(int[][] grid, boolean[][] visited, int x, int y, int mark) {
        if (visited[x][y] || grid[x][y] == 0) return; // 終止條件：訪問(wèn)過(guò)的節(jié)點(diǎn) 或者 遇到海水
        visited[x][y] = true; // 標(biāo)記訪問(wèn)過(guò)
        grid[x][y] = mark; // 給陸地標(biāo)記新標(biāo)簽
        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.length || nexty < 0 || nexty >= grid[0].length) continue;  // 越界了，直接跳過(guò)
            dfs(grid, visited, nextx, nexty, mark);
        }
    }

    public int largestIsland(int[][] grid) {
        int n = grid.length, m = grid[0].length;
        boolean[][] visited = new boolean[n][m]; // 標(biāo)記訪問(wèn)過(guò)的點(diǎn)
        Map<Integer, Integer> gridNum = new HashMap<>();
        int mark = 2; // 記錄每個(gè)島嶼的編號(hào)
        boolean isAllGrid = true; // 標(biāo)記是否整個(gè)地圖都是陸地

        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); // 將與其鏈接的陸地都標(biāo)記上
                    gridNum.put(mark, count); // 記錄每一個(gè)島嶼的面積
                    mark++; // 記錄下一個(gè)島嶼編號(hào)
                }
            }
        }

        if (isAllGrid) return n * m; // 如果整個(gè)地圖都是陸地，返回總面積

        int maxArea = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 0) {
                    Set<Integer> seen = new HashSet<>();
                    int area = 1; // 將這個(gè)0變?yōu)?后的新面積
                    for (int k = 0; k < 4; k++) {
                        int nextx = i + dir[k][0];
                        int nexty = j + dir[k][1];
                        if (nextx >= 0 && nextx < n && nexty >= 0 && nexty < m && grid[nextx][nexty] > 1) {
                            int id = grid[nextx][nexty];
                            if (!seen.contains(id)) {
                                area += gridNum.get(id);
                                seen.add(id);
                            }
                        }
                    }
                    maxArea = Math.max(maxArea, area);
                }
            }
        }
        return maxArea;
    }

第二步過(guò)程如圖所示：
image.png

也就是遍歷每一個(gè)0的方格，并統(tǒng)計(jì)其相鄰島嶼面積，最后取一個(gè)最大值。

這個(gè)過(guò)程的時(shí)間復(fù)雜度也為 n * n。

所以整個(gè)解法的時(shí)間復(fù)雜度，為 n * n + n * n 也就是 n^2。

當(dāng)然這里還有一個(gè)優(yōu)化的點(diǎn)，就是 可以不用 visited數(shù)組，因?yàn)橛衜ark來(lái)標(biāo)記，所以遍歷過(guò)的grid[i][j]是不等于1的。

代碼如下：

import java.util.*;

public class Solution {
    static int count;
    static int n, m;
    static int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}}; // 四個(gè)方向

    public static void dfs(int[][] grid, int x, int y, int mark) {
        if (grid[x][y] != 1 || grid[x][y] == 0) return; // 終止條件：訪問(wèn)過(guò)的節(jié)點(diǎn) 或者 遇到海水
        grid[x][y] = mark; // 給陸地標(biāo)記新標(biāo)簽
        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;  // 越界了，直接跳過(guò)
            dfs(grid, nextx, nexty, mark);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        int[][] grid = new int[n][m];

        // 讀取網(wǎng)格數(shù)據(jù)
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                grid[i][j] = sc.nextInt();
            }
        }

        Map<Integer, Integer> gridNum = new HashMap<>();
        int mark = 2; // 記錄每個(gè)島嶼的編號(hào)
        boolean isAllGrid = true; // 標(biāo)記是否整個(gè)地圖都是陸地

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 0) isAllGrid = false;
                if (grid[i][j] == 1) {
                    count = 0;
                    dfs(grid, i, j, mark); // 將與其鏈接的陸地都標(biāo)記上
                    gridNum.put(mark, count); // 記錄每一個(gè)島嶼的面積
                    mark++; // 記錄下一個(gè)島嶼編號(hào)
                }
            }
        }
    }
}

整體代碼如下：

import java.util.*;

public class Main {
    static int n, m;
    static int count;
    static int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}}; // 四個(gè)方向

    public static void dfs(int[][] grid, boolean[][] visited, int x, int y, int mark) {
        if (visited[x][y] || grid[x][y] == 0) return; // 終止條件：訪問(wèn)過(guò)的節(jié)點(diǎn) 或者 遇到海水
        visited[x][y] = true; // 標(biāo)記訪問(wèn)過(guò)
        grid[x][y] = mark; // 給陸地標(biāo)記新標(biāo)簽
        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;  // 越界了，直接跳過(guò)
            dfs(grid, visited, nextx, nexty, mark);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        int[][] grid = new int[n][m];

        // 讀取網(wǎng)格數(shù)據(jù)
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                grid[i][j] = sc.nextInt();
            }
        }

        boolean[][] visited = new boolean[n][m]; // 標(biāo)記訪問(wèn)過(guò)的點(diǎn)
        Map<Integer, Integer> gridNum = new HashMap<>();
        int mark = 2; // 記錄每個(gè)島嶼的編號(hào)
        boolean isAllGrid = true; // 標(biāo)記是否整個(gè)地圖都是陸地

        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); // 將與其鏈接的陸地都標(biāo)記上
                    gridNum.put(mark, count); // 記錄每一個(gè)島嶼的面積
                    mark++; // 記錄下一個(gè)島嶼編號(hào)
                }
            }
        }

        if (isAllGrid) {
            System.out.println(n * m); // 如果都是陸地，返回全面積
            return; // 結(jié)束程序
        }

        // 以下邏輯是根據(jù)添加陸地的位置，計(jì)算周邊島嶼面積之和
        int result = 0; // 記錄最后結(jié)果
        Set<Integer> visitedGrid = new HashSet<>(); // 標(biāo)記訪問(wèn)過(guò)的島嶼
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                count = 1; // 記錄連接之后的島嶼數(shù)量
                visitedGrid.clear(); // 每次使用時(shí)，清空
                if (grid[i][j] == 0) {
                    for (int k = 0; k < 4; k++) {
                        int neari = i + dir[k][1]; // 計(jì)算相鄰坐標(biāo)
                        int nearj = j + dir[k][0];
                        if (neari < 0 || neari >= n || nearj < 0 || nearj >= m) continue;
                        if (visitedGrid.contains(grid[neari][nearj])) continue; // 添加過(guò)的島嶼不要重復(fù)添加
                        // 把相鄰四面的島嶼數(shù)量加起來(lái)
                        count += gridNum.getOrDefault(grid[neari][nearj], 0);
                        visitedGrid.add(grid[neari][nearj]); // 標(biāo)記該島嶼已經(jīng)添加過(guò)
                    }
                }
                result = Math.max(result, count);
            }
        }
        System.out.println(result);
    }
}
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容