Re: [閒聊] 每日leetcode

[DJYOMIYAHINA (通通打死)]

想不到
直接看hint 很簡潔明瞭
最多兩個0就可以切出一個獨立的island
我怎麼沒想到
我是智障

class Solution {
public:
    int m;
    int n;

    void dfs(vector<vector<int>>& grid, int i, int j) {

        if (grid[i][j] == -1 || grid[i][j] == 0) {
            return;
        }

        grid[i][j] = -1;
        int delta[5] = {0, 1, 0, -1, 0};
        for (int k=0; k<4; k++) {
            int next_i = i+delta[k];
            int next_j = j+delta[k+1];

            if (0<=next_i && next_i<this->m && 0<=next_j && next_j<this->n) {
                dfs(grid, next_i, next_j);
            }
        }
        return;
    }

    int numofIsland(vector<vector<int>>& grid) {
        int num = 0;
        for (int i=0; i<this->m; i++) {
            for (int j=0; j<this->n; j++) {
                if (grid[i][j] == 1) {
                    dfs(grid, i, j);
                    num += 1;
                }
            }
        }

        // reset grid
        for (int i=0; i<this->m; i++) {
            for (int j=0; j<this->n; j++) {
                if (grid[i][j] == -1) {
                    grid[i][j] = 1;
                }
            }
        }

        return num;
    }

    int minDays(vector<vector<int>>& grid) {
        this->m = grid.size();
        this->n = grid[0].size();

        if (numofIsland(grid) != 1) {
            return 0;
        }

        for(int i=0; i<this->m; i++) {
            for(int j=0; j<this->n; j++) {
                if(grid[i][j] == 1) {
                    grid[i][j] = 0;
                    if (numofIsland(grid) != 1) {
                        return 1;
                    }
                    grid[i][j] = 1;
                }
            }
        }

        return 2;
    }
};

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 125.229.37.69 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1723385921.A.61F.html
推 Smallsh: 大師
推 JIWP: 別倦了
推 sustainer123: 大師
推 rainkaras: 7
推 oin1104: 大師
推 dont: 大師