代碼隨想錄圖論 第三天 | 130. 被圍繞的區(qū)域 417. 太平洋大西洋水流問題

一、130. 被圍繞的區(qū)域

題目鏈接：https://leetcode.cn/problems/surrounded-regions/
思路：題目要求沾邊的不動(dòng)，只改沒沾邊的，那么可以先dfs遍歷4條邊，把沾邊的O都改成A。然后直接兩層for循環(huán)遍歷整個(gè)數(shù)組，把O該成X，把A改成O。

class Solution {
     public void solve(char[][] board) {
        for (int i = 0; i < board.length; i++) {
            if (board[i][0] == 'O') dfs(board, i, 0);
            if (board[i][board[0].length-1] == 'O') dfs(board, i, board[0].length-1);
        }
        for (int i = 0; i < board[0].length; i++) {
            if (board[0][i] == 'O') dfs(board, 0, i);
            if (board[board.length-1][i] == 'O') dfs(board, board.length-1, i);
        }
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == 'O') board[i][j] = 'X';
                if (board[i][j] == 'A') board[i][j] = 'O';
            }
        }
    }

    void dfs(char[][] board, int x, int y) {
        if (x < 0 || x >= board.length || y < 0 || y >= board[0].length || board[x][y] != 'O') {
            return;
        }
        board[x][y] = 'A';
        dfs(board, x-1, y);
        dfs(board, x+1, y);
        dfs(board, x, y-1);
        dfs(board, x, y+1);
    }
}

二、417. 太平洋大西洋水流問題

題目鏈接：https://leetcode.cn/problems/pacific-atlantic-water-flow/
思路：分別從太平洋和大西洋的邊界出發(fā)，逆流而上進(jìn)行分開的標(biāo)記，只要某個(gè)格子即被太平洋標(biāo)記又被大西洋標(biāo)記即可收取。文章來源地址http://www.zghlxwxcb.cn/news/detail-725934.html

class Solution {
    boolean[][][] visited;
    int[][] nums = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        List<List<Integer>> arrayLists = new ArrayList<>();
        visited = new boolean[heights.length][heights[0].length][2];
        for (int i = 0; i < heights.length; i++) {
            visited[i][0][0] = true;
            dfs(heights, i, 0, 0);
            visited[i][heights[0].length-1][1] = true;
            dfs(heights, i, heights[0].length-1, 1);
        }
        for (int i = 0; i < heights[0].length; i++) {
            visited[0][i][0] = true;
            dfs(heights, 0, i, 0);
            visited[heights.length-1][i][1] = true;
            dfs(heights, heights.length-1, i,1);
        }
        for (int i = 0; i < heights.length; i++) {
            for (int j = 0; j < heights[0].length; j++) {
                if (visited[i][j][0] && visited[i][j][1]) {
                    List<Integer> list = new ArrayList<>();
                    list.add(i);
                    list.add(j);
                    arrayLists.add(list);
                }
            }
        }
        return arrayLists;
    }

    void dfs(int[][] heights, int x, int y, int sign) {
        for (int[] num : nums) {
            int nX = x + num[0];
            int nY = y + num[1];
            if (nX < 0 || nX >= heights.length || nY < 0 || nY >= heights[0].length) {
                continue;
            }
            if (visited[nX][nY][sign] || heights[nX][nY] < heights[x][y]) continue;
            visited[nX][nY][sign] = true;
            dfs(heights, nX, nY, sign);
        }
    }
}

到了這里，關(guān)于代碼隨想錄圖論 第三天 | 130. 被圍繞的區(qū)域 417. 太平洋大西洋水流問題的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！