乐趣区

关于leetcode:leetcode-130-Surrounded-Regions-被围绕的区域中等

jiezi

一、题目粗心

标签: 搜寻

https://leetcode.cn/problems/surrounded-regions

给你一个 m x n 的矩阵 board，由若干字符 ‘X’ 和 ‘O’，找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。

示例 1：

输出：board = [[“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”]]
解释：被围绕的区间不会存在于边界上，换句话说，任何边界上的 ‘O’ 都不会被填充为 ‘X’。任何不在边界上，或不与边界上的 ‘O’ 相连的 ‘O’ 最终都会被填充为 ‘X’。如果两个元素在程度或垂直方向相邻，则称它们是“相连”的。

示例 2：

输出：board = [[“X”]]
输入：[[“X”]]

提醒：

  • m == board.length
  • n == board[i].length
  • 1 <= m, n <= 200

  • boardi 为 ‘X’ 或 ‘O’

    二、解题思路

    找联通重量问题用 DFS 来做，次要是细节的优化。能够从这个中央动手，任何不在边界上的 O 都会变成 X。也能够反向思维先找没有被突围的。具体的实现思路：从边界登程，去找和边界相连的 O，把它标记成一个非凡值，再把网格中其余的 O 标记成 X，最初再把第一步标记成非凡值的 O 还原

    三、解题办法

    3.1 Java 实现 

    public class Solution {public void solve(char[][] board) {
      this.m = board.length;
      if (this.m == 0) {return;}
      this.board = board;
      this.n = board[0].length;

      for (int y = 0; y < m; y++) {dfs(0, y);
          dfs(n - 1, y);
      }

      for (int x = 0; x < n; x++) {dfs(x, 0);
          dfs(x, m - 1);
      }

      Map<Character, Character> v = new HashMap<>();
      v.put('G', 'O');
      v.put('O', 'X');
      v.put('X', 'X');
      for (int y = 0; y < m; y++) {for (int x = 0; x < n; x++) {switch (board[y][x]) {
                  case 'G':
                      board[y][x] = 'O';
                      break;
                  case 'O':
                      board[y][x] = 'X';
                      break;
                  case 'X':
                      board[y][x] = 'X';
              }
          }
      }
  }

  private char[][] board;
  private int m;
  private int n;

  private void dfs(int x, int y) {if (x < 0 || x >= n || y < 0 || y >= m || board[y][x] != 'O') {return;}
      board[y][x] = 'G';
      dfs(x - 1, y);
      dfs(x + 1, y);
      dfs(x, y - 1);
      dfs(x, y + 1);
  }
}

    四、总结小记

  • 2022/6/10 联通重量问题用 DFS
退出移动版