thảo luận Leetcode mỗi ngày

class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])

        def dfs(node):
            flag = True
            visited.add(node)

            x, y = node
            if x == 0 or x == m - 1 or y == 0 or y == n - 1:
                flag = False

            directions = [(-1, 0), (1, 0), (0, 1), (0, -1)]

            for u, v in directions:
                if 0 <= x + u < m and 0 <= y + v < n and (x + u, y + v) not in visited and grid[x + u][y + v] == 0:
                    if not dfs((x + u, y + v)):
                        flag = False

            return flag

        visited = set()
        res = 0
        
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 0 and (i, j) not in visited:
                    if dfs((i, j)):
                        res += 1

        return res

function closedIsland(grid: number[][]): number {
    const m = grid.length, n = grid[0].length;
    const visited: boolean[][] = [];
    for (let i = 0; i < m; i++) {
        visited[i] = [];
        for (let j = 0; j < n; j++) {
            visited[i].push(false);
        }
    }
    let ans = 0;
    const bfs = (x: number, y: number): boolean => {
        const queue: number[][] = [];
        let isAdd = true;
        queue.push([x, y]);
        visited[x][y] = true;
        const dX = [0, 1, 0, -1];
        const dY = [-1, 0, 1, 0];
        while (queue.length) {
            const item = queue.shift();
            for (let i = 0; i < 4; i++) {
                const row = item[0] + dX[i];
                const col = item[1] + dY[i]
                if (row < 0 || row >= m || col < 0 || col >= n) {
                    isAdd = false;
                } else if (grid[row][col] === 0 && !visited[row][col]) {
                    queue.push([row, col])
                    visited[row][col] = true
                }
            }
        }
        return isAdd;

    }
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (grid[i][j] === 0 && !visited[i][j] && bfs(i, j)) {
                ans++
            }
        }
    }
    return ans;
};

class Solution {
public:
    bool visited[101][101] = {0};
    int movex[4] = {-1, 1, 0, 0};
    int movey[4] = {0, 0, -1, 1};

    bool dfs(int x, int y, int m, int n, vector<vector<int>>& grid) {
        visited[x][y] = true;

        bool ans = true;
        if (x == 0 || x == m - 1 || y == 0 || y == n - 1) ans = false;

        for (int i = 0; i < 4; i++) {
            int newx = x + movex[i];
            int newy = y + movey[i];

            if (newx >= 0 && newx <= m - 1 && newy >= 0 && newy <= n - 1)
                if ((!visited[newx][newy]) && (grid[newx][newy] == 0))
                    ans &= dfs(newx, newy, m, n, grid);
        }

        return ans;
    }

    int closedIsland(vector<vector<int>>& grid) {
        int ans = 0;
        int m = grid.size();
        int n = grid[0].size();

        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if ((!visited[i][j]) && (grid[i][j] == 0))
                    if (dfs(i, j, m, n, grid)) ans++;

        return ans;
    }
};

class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        dirs = [(1,0),(0,1),(-1,0),(0,-1)]
        m, n = len(grid), len(grid[0])

        def dfs(i, j):
            nonlocal visit, res
            if (
                (i, j) in visit or
                i < 0 or i == m or
                j < 0 or j == n or
                grid[i][j] == 1
            ): return False
            visit.add((i, j))
            if i == 0 or i == m-1 or j == 0 or j == n-1:
                res = 0
            for di,dj in dirs:
                ni,nj = i+di,j+dj
                if (ni,nj) not in visit:
                    dfs(ni,nj)

        cnt = 0
        visit = set()
        res = 1
        for i in range(m):
            for j in range(n):
                if (i,j) not in visit and grid[i][j] == 0 and i != 0 and i != m-1 and j != 0 and j != n-1:
                    dfs(i,j)
                    cnt += res
                    res = 1
        return cnt

function numEnclaves(grid: number[][]): number {
    const m = grid.length, n = grid[0].length;
    const visited: boolean[][] = [];
    for (let i = 0; i < m; i++) {
        visited[i] = [];
        for (let j = 0; j < n; j++) {
            visited[i].push(false);
        }
    }
    let ans = 0;
    const bfs = (x: number, y: number) => {
        const queue: number[][] = [];
        queue.push([x, y]);
        visited[x][y] = true;
        const dX = [0, 1, 0, -1];
        const dY = [-1, 0, 1, 0];
        while (queue.length) {
            const item = queue.shift();
            for (let i = 0; i < 4; i++) {
                const row = item[0] + dX[i];
                const col = item[1] + dY[i]
                if (row < 0 || row >= m || col < 0 || col >= n) {
                    continue
                } else if (grid[row][col] === 1 && !visited[row][col]) {
                    queue.push([row, col])
                    visited[row][col] = true
                }
            }
        }
        return;

    }
    for (let i = 0; i < m; ++i) {
        if (grid[i][0] == 1 && !visited[i][0]) {
            bfs(i, 0);
        }

        if (grid[i][n - 1] == 1 && !visited[i][n - 1]) {
            bfs(i, n - 1);
        }
    }

    for (let i = 0; i < n; ++i) {
        if (grid[0][i] == 1 && !visited[0][i]) {
            bfs(0, i);
        }
        if (grid[m - 1][i] == 1 && !visited[m - 1][i]) {
            bfs(m - 1, i);
        }
    }
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (grid[i][j] == 1 && !visited[i][j]) {
                ans++;
            }
        }
    }
    return ans;
};

function numEnclaves(grid: number[][]): number {
    const [m, n] = [grid.length, grid[0].length];
    let result = 0;
    let count = 0;

    const dfs = (r: number, c: number): boolean => {
        if (
            r < 0 || c < 0
            || r === m || c === n
        ) {
            return false;
        }

        if (grid[r][c] === 0 || grid[r][c] === -1) {
            return true;
        }

        grid[r][c] = -1;
        count++;

        const dirX = [0, 1, 0, -1];
        const dirY = [-1, 0, 1, 0];
        let isClosed = true;
        for (let i = 0; i < 4; i++) {
            if (!dfs(r + dirX[i], c + dirY[i])) {
                isClosed = false;
            }
        }

        return isClosed;
    }

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            count = 0;

            if (grid[i][j] === 1 && grid[i][j] !== -1 && dfs(i, j)) {
                result += count;
            }
        }
    }

    return result;
};

class Solution {
private:
    int dx[4] = {1, 0, -1, 0};
    int dy[4] = {0, 1, 0, -1};
    bool closed;
    int count, rows, cols, tmp;
    void dfs(vector<vector<int>>& grid, int i, int j){       
        for(int k = 0; k < 4; ++k){
            int ni = i + dx[k], nj = j + dy[k];
            if(ni < 0 || nj < 0 || ni >= rows || nj >= cols || !grid[ni][nj])
                continue;
            if(ni == 0 || nj == 0 || ni == rows - 1 || nj == cols - 1)
                closed = false;
            ++tmp;
            grid[ni][nj] = 0;
            dfs(grid, ni, nj);
        }
    }
public:
    int numEnclaves(vector<vector<int>>& grid) {
        count = 0, rows = grid.size(), cols = grid[0].size();
        for(int i = 0; i < rows; ++i){
            for(int j = 0; j < cols; ++j){
                if(!grid[i][j]) continue;
                grid[i][j] = 0;
                closed = true;
                tmp = 1;
                if(i == 0 || j == 0 || i == rows - 1 || j == cols - 1)
                    closed = false;
                dfs(grid, i, j);
                if(closed) count += tmp;
            }
        }
        return count;
    }
};

class Solution_DFS_recursive:
    def numEnclaves(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])

        def dfs(node):
            flag = True
            visited.add(node)
            s.add(node)
            x, y = node
            if x == 0 or x == m - 1 or y == 0 or y == n - 1:
                flag = False

            directions = [(-1, 0), (1, 0), (0, 1), (0, -1)]

            for u, v in directions:
                if 0 <= x + u < m and 0 <= y + v < n and (x + u, y + v) not in visited and grid[x + u][y + v] == 1:
                    if not dfs((x + u, y + v)):
                        flag = False

            return flag

        res = 0
        visited = set()
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1 and (i, j) not in visited:
                    s = set()
                    if dfs((i, j)):
                        res += len(s)         

        return res

class Solution_DFS_interative:
    def numEnclaves(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])

        res = 0
        visited = set()
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1 and (i, j) not in visited:
                    s = set()
                    stack = [(i, j)]
                    flag = True
                    while stack:
                        x, y = stack.pop()
                        s.add((x, y))
                        if x == 0 or x == m - 1 or y == 0 or y == n - 1:
                            flag = False

                        directions = [(-1, 0), (1, 0), (0, 1), (0, -1)]
                        for u, v in directions:
                            if 0 <= x + u < m and 0 <= y + v < n and (x + u, y + v) not in visited and grid[x + u][y + v] == 1:
                                visited.add((x + u, y + v))
                                stack.append((x + u, y + v))
                    if flag:
                        res += len(s)
        return res

    def numEnclaves(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        visited = [[False]*n for i in range(m)]

        def dfs(row,col):
            if(row<0 or col<0 or row>=m or col>=n or grid[row][col]==0 or visited[row][col]==True):
                return
            visited[row][col] = True
            dfs(row,col-1)
            dfs(row+1,col)
            dfs(row,col+1)
            dfs(row-1,col)

        # first row and last row
        for j in range(n):
            if(grid[0][j]==1):
                dfs(0,j)
            if(grid[m-1][j]==1):
                dfs(m-1,j)
        for i in range(m):
            if(grid[i][0]==1):
                dfs(i,0)
            if(grid[i][n-1]==1):
                dfs(i,n-1)
        count = 0
        for i in range(m):
            for j in range(n):
                if(grid[i][j]==1 and not visited[i][j]):
                    count+=1
        return count

/**
 * @param {number[][]} grid
 * @return {number}
 */
var numEnclaves = function(grid) {
    const m = grid.length, n = grid[0].length;
    const dirs = [[-1, 0], [1, 0], [0, 1], [0, -1]];
    let ans = 0;
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (grid[i][j] === 1) {
                let closed = true;
                let cntr = 0;
                const q = new Queue();
                q.push([i, j]);
                grid[i][j] = -1;
                while (!q.isEmpty()) {
                    const [ni, nj] = q.pop();
                    cntr++;
                    for (const [ii, jj] of dirs.map(d => [ni + d[0], nj + d[1]])) {
                        if (ii < 0 || ii >= m || jj < 0 || jj >= n) {
                            closed = false;
                        } else if (grid[ii][jj] === 1) {
                            grid[ii][jj] = -1;
                            q.push([ii, jj]);
                        }
                    }
                }
                ans += closed ? cntr : 0;
            }
        }
    }
    return ans;
};