↓快轉到主要內容
  1. Leetcode/

[LeetCode] 1568. Minimum Number of Days to Disconnect Island

·
LeetCode DFS
目錄

題目連結：1568. Minimum Number of Days to Disconnect Island

題目敘述
#

You are given an m x n binary grid grid where 1 represents land and 0 represents water. An island is a maximal 4-directionally (horizontal or vertical) connected group of 1’s.

The grid is said to be connected if we have exactly one island, otherwise is said disconnected.

In one day, we are allowed to change any single land cell (1) into a water cell (0).

Return the minimum number of days to disconnect the grid.

解題思路
#

程式碼
#

C++
#

class Solution {
public:
    int m, n;
    int ones; // number of one in grid
    int component; // number of component
    int ap_cnt; // number of articulation points
    int dfn_cnt;
    vector<vector<int>> dfn, low;
    int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};

    // Tarjan's Algorithm
    void dfs(int y, int x, int py, int px, vector<vector<int>>& grid) {
        int child = 0;
        bool is_ap = false;

        // 把走過的節點標號，low 預設為自己的編號
        dfn[y][x] = low[y][x] = ++dfn_cnt; 
        ones++;

        for (int i = 0; i < 4; i++) {
            int ny = y + dir[i][0];
            int nx = x + dir[i][1];

            if (ny < 0 || ny >= m || nx < 0 || nx >= n || grid[ny][nx] == 0)
                continue;

            if (!dfn[ny][nx]) { // 還沒走過的點
                child++;
                dfs(ny, nx, y, x, grid);
                low[y][x] = min(low[y][x], low[ny][nx]);

                if (low[ny][nx] >= dfn[y][x]) {
                    // 節點 (ny,nx) 回不到比 (y,x) 更早的祖先，因此 (y,x) 是關節點
                    is_ap = true;
                }
            } else if (ny != py || nx != px) { 
                // 已走過的點，且該點不等於父節點
                low[y][x] = min(low[y][x], dfn[ny][nx]); // 嘗試能不能回到更上層的祖先
            }
        }

        if (y == py && x == px && child > 1) {
            // 節點為 DFS tree 的 root，且有兩個以上的子樹
            ap_cnt++;
        } else if ((y !=py || x != px) && is_ap) {
            // 節點不是 DFS tree 的 root
            ap_cnt++;
        }
    }

    int minDays(vector<vector<int>>& grid) {
        m = grid.size();
        n = grid[0].size();
        dfn.resize(m, vector<int>(n));
        low.resize(m, vector<int>(n));

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1 && !dfn[i][j]) {
                    dfs(i, j, i, j, grid);
                    component++;
                }
            }
        }

        if (component > 1) {
            return 0;
        } else if (ones <= 2) {
            return ones;
        } else {
            return ap_cnt ? 1 : 2;
        }
    }
};