【LeetCode】回溯问题：二维平面类型

灰太狼 2022-10-29 09:13 3阅读 0赞

### 二维平面 ###

#### [79. 单词搜索][79.] ####

难度中等774收藏分享切换为英文接收动态反馈

给定一个二维网格和一个单词，找出该单词是否存在于网格中。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

**示例:**

board =
    [
      ['A','B','C','E'],
      ['S','F','C','S'],
      ['A','D','E','E']
    ]
    
    给定 word = "ABCCED", 返回 true
    给定 word = "SEE", 返回 true
    给定 word = "ABCB", 返回 false

**题解**

class Solution { 
        public boolean exist(char[][] board, String word) { 
            boolean[][] path = new boolean[board.length][board[0].length];
            for(int i = 0 ; i < board.length ; i ++){ 
                for(int j = 0 ; j < board[0].length ; j ++){ 
                    if(isFind(board , 0 , word , i , j , path)){ 
                        return true;
                    }
                }
            }
            return false;
        }
    
        boolean isFind(char[][] board , int idx , String word , int idx1 , int idx2 , boolean[][] path){ 
            if(word.length() == idx){ 
                return true;
            }
    
            if(idx1 == board.length || idx2 == board[0].length || idx1 < 0 || idx2 < 0 || path[idx1][idx2] 
                    || board[idx1][idx2] != word.charAt(idx)){ 
                return false;
            }
    
            path[idx1][idx2] = true;
            boolean res = isFind(board , idx + 1 , word , idx1 + 1 , idx2, path)
                            || isFind(board ,idx + 1 , word , idx1 , idx2 + 1, path)
                            || isFind(board , idx + 1 , word , idx1 - 1 , idx2 , path)
                            || isFind(board , idx + 1 , word , idx1 , idx2 - 1, path);
            path[idx1][idx2] = false;
    
            return res;
        }
    }

#### [200. 岛屿数量][200.] ####

难度中等971收藏分享切换为英文接收动态反馈

给你一个由 `'1'`（陆地）和 `'0'`（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

**示例 1：**

输入：grid = [
      ["1","1","1","1","0"],
      ["1","1","0","1","0"],
      ["1","1","0","0","0"],
      ["0","0","0","0","0"]
    ]
    输出：1

**示例 2：**

输入：grid = [
      ["1","1","0","0","0"],
      ["1","1","0","0","0"],
      ["0","0","1","0","0"],
      ["0","0","0","1","1"]
    ]
    输出：3

**题解**

class Solution { 
        public int numIslands(char[][] grid) { 
            boolean[][] bitmap = new boolean[grid.length][grid[0].length];
            int res = 0 ;
    
            for(int i = 0 ; i < grid.length ; i ++){ 
                for(int j = 0 ; j < grid[0].length ; j ++){ 
                    if(!bitmap[i][j] && grid[i][j] == '1'){ 
                        res ++;
                        func(i , j , bitmap , grid);
                    }        
                }
            }
    
            return res;
        }
    
        void func(int idx1 , int idx2 , boolean[][] bitmap , char[][] grid){ 
            if(idx1 == grid.length || idx2 == grid[0].length || idx1 < 0 || idx2 < 0){ 
                return;
            }
    
            if(grid[idx1][idx2] == '0' || bitmap[idx1][idx2]){ 
                return;
            }
    
            bitmap[idx1][idx2] = true;
            func(idx1 + 1 , idx2 , bitmap , grid);
            func(idx1 , idx2 + 1 , bitmap , grid);
            func(idx1 - 1 , idx2 , bitmap , grid);
            func(idx1 , idx2 - 1, bitmap, grid);
        }
    }

#### [130. 被围绕的区域][130.] ####

难度中等470收藏分享切换为英文接收动态反馈

给定一个二维的矩阵，包含 `'X'` 和 `'O'`（**字母 O**）。

找到所有被 `'X'` 围绕的区域，并将这些区域里所有的 `'O'` 用 `'X'` 填充。

**示例:**

X X X X
    X O O X
    X X O X
    X O X X

运行你的函数后，矩阵变为：

X X X X
    X X X X
    X X X X
    X O X X

**题解**

class Solution { 
        public void solve(char[][] board) { 
            for(int i = 0 ; i <  board.length ; i ++){ 
                for(int j = 0 ; j < board[0].length ; j ++){ 
                    if((i - 1 < 0 || i + 1 == board.length || j - 1 < 0 || j + 1 == board[0].length) && board[i][j] == 'O' ){ 
                        func(i , j , board);
                    }
                }
    
            }
    
            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] == '!'){ 
                        board[i][j] = 'O';
                    }
                }
            }
        }
    
        void func(int idx1 , int idx2 , char[][] board){ 
            if(idx1 == board.length || idx2 == board[0].length || idx1 < 0 || idx2 < 0){ 
                return;
            }
    
            if(board[idx1][idx2] != 'O'){ 
                return;
            }
            board[idx1][idx2] = '!';
    
            func(idx1 + 1 , idx2 , board);
            func(idx1 , idx2 + 1 , board);
            func(idx1 - 1 , idx2 , board);
            func(idx1 , idx2 - 1, board);
        }
    }

#### [417. 太平洋大西洋水流问题][417.] ####

难度中等196收藏分享切换为英文接收动态反馈

给定一个 `m x n` 的非负整数矩阵来表示一片大陆上各个单元格的高度。“太平洋”处于大陆的左边界和上边界，而“大西洋”处于大陆的右边界和下边界。

规定水流只能按照上、下、左、右四个方向流动，且只能从高到低或者在同等高度上流动。

请找出那些水流既可以流动到“太平洋”，又能流动到“大西洋”的陆地单元的坐标。

**提示：**

1.  输出坐标的顺序不重要
2.  *m* 和 *n* 都小于150

**示例：**

给定下面的 5x5 矩阵:
    
      太平洋 ~   ~   ~   ~   ~ 
           ~  1   2   2   3  (5) *
           ~  3   2   3  (4) (4) *
           ~  2   4  (5)  3   1  *
           ~ (6) (7)  1   4   5  *
           ~ (5)  1   1   2   4  *
              *   *   *   *   * 大西洋
    
    返回:
    
    [[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (上图中带括号的单元).

**题解**

class Solution { 
        public List<List<Integer>> pacificAtlantic(int[][] matrix) { 
            List<List<Integer>> res = new ArrayList<>();
            if(matrix.length == 0){ 
                return res;
            }
            boolean[][] path = new boolean[matrix.length][matrix[0].length];
    
            boolean[][] canToDXY = new boolean[matrix.length][matrix[0].length];
            boolean[][] canToTPY = new boolean[matrix.length][matrix[0].length];
    
            for(int i = 0 ; i < matrix.length ; i ++){ 
                for(int j = 0 ; j < matrix[0].length ; j ++){ 
                    canToDXY[i][j] = func(i , j , matrix , path , true);
                    canToTPY[i][j] = func(i , j , matrix , path , false);
    
                    if(canToDXY[i][j] && canToTPY[i][j]){ 
                        List<Integer> l = new ArrayList<>();
                        l.add(i);
                        l.add(j);
                        res.add(l);
                    }
                }
            }
            
            return res;
        }
    
        boolean func(int idx1 , int idx2 , int[][] matrix , boolean[][] path , boolean isToDXY){ 
            if((isToDXY && (idx1 + 1 == matrix.length || idx2 + 1 == matrix[0].length))
                    || ( ! isToDXY && (idx1 - 1 < 0 || idx2 - 1 < 0))){ 
                return true;
            }
            
            if(path[idx1][idx2]){ 
                return false;
            }
    
            boolean canTo = false;
            path[idx1][idx2] = true;
    
            if(idx1 + 1 < matrix.length && matrix[idx1][idx2] >= matrix[idx1 + 1][idx2]){ 
                canTo = canTo || func(idx1 + 1 , idx2 , matrix , path , isToDXY);
            }
            if(idx2 + 1 < matrix[0].length &&matrix[idx1][idx2] >= matrix[idx1][idx2 + 1]){ 
                canTo = canTo || func(idx1 , idx2 + 1 , matrix , path , isToDXY);
            }
            if(idx1 - 1 >= 0 && matrix[idx1][idx2] >= matrix[idx1 - 1][idx2]){ 
                canTo = canTo || func(idx1 - 1 , idx2 , matrix , path , isToDXY);
            }
            if(idx2 - 1 >= 0 && matrix[idx1][idx2] >= matrix[idx1][idx2 - 1]){ 
                canTo = canTo || func(idx1 , idx2 - 1, matrix , path , isToDXY);
            }
    
            path[idx1][idx2] = false;
            return canTo;
        }
    }

[79.]: https://leetcode-cn.com/problems/word-search/
[200.]: https://leetcode-cn.com/problems/number-of-islands/
[130.]: https://leetcode-cn.com/problems/surrounded-regions/
[417.]: https://leetcode-cn.com/problems/pacific-atlantic-water-flow/