今天和大家聊的问题叫做 被围绕的区域，我们先来看题面：https://leetcode-cn.com/problems/surrounded-regions/
Given a 2D board containing 'X' and 'O' (the letter O), capture all regions surrounded by 'X'.
A region is captured by flipping all 'O's into 'X's in that surrounded region.
题意
给定一个二维的矩阵，包含 '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 解释: 被围绕的区间不会存在于边界上， 换句话说，任何边界上的 'O' 都不会被填充为 'X'。任何不在边界上， 或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。 如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。
解题
从边界出发把,先把边界上和O连通点找到, 把这些变成B,然后遍历整个board把O变成X, 把B变成O如下图所示
思路一: DFS
class Solution { int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; public void solve(char[][] board) { if (board == null || board.length == 0 || board[0] == null || board[0].length == 0) return; int row = board.length; int col = board[0].length; for (int j = 0; j < col; j++) { // 第一行 if (board[0][j] == 'O') dfs(0, j, board, row, col); // 最后一行 if (board[row - 1][j] == 'O') dfs(row - 1, j, board, row, col); } for (int i = 0; i < row; i++) { // 第一列 if (board[i][0] == 'O') dfs(i, 0, board, row, col); // 最后一列 if (board[i][col - 1] == 'O') dfs(i, col - 1, board, row, col); } // 转变 for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { if (board[i][j] == 'O') board[i][j] = 'X'; if (board[i][j] == 'B') board[i][j] = 'O'; } } } private void dfs(int i, int j, char[][] board, int row, int col) { board[i][j] = 'B'; for (int[] dir : dirs) { int tmp_i = dir[0] + i; int tmp_j = dir[1] + j; if (tmp_i < 0 || tmp_i >= row || tmp_j < 0 || tmp_j >= col || board[tmp_i][tmp_j] != 'O') continue; dfs(tmp_i, tmp_j, board, row, col); } } }
思路二: BFS
class Solution { int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; private static class Point { int x, y; Point(int x, int y) { this.x = x; this.y = y; } } public void solve(char[][] board) { if (board == null || board.length == 0 || board[0] == null || board[0].length == 0) return; int row = board.length; int col = board[0].length; for (int j = 0; j < col; j++) { // 第一行 if (board[0][j] == 'O') bfs(0, j, board, row, col); // 最后一行 if (board[row - 1][j] == 'O') bfs(row - 1, j, board, row, col); } for (int i = 0; i < row; i++) { // 第一列 if (board[i][0] == 'O') bfs(i, 0, board, row, col); // 最后一列 if (board[i][col - 1] == 'O') bfs(i, col - 1, board, row, col); } // 转变 for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { if (board[i][j] == 'O') board[i][j] = 'X'; if (board[i][j] == 'B') board[i][j] = 'O'; } } } private void bfs(int i, int j, char[][] board, int row, int col) { Deque<Point> queue = new LinkedList<>(); queue.offer(new Point(i, j)); while (!queue.isEmpty()) { Point tmp = queue.poll(); if (tmp.x >= 0 && tmp.x < row && tmp.y >= 0 && tmp.y < col && board[tmp.x][tmp.y] == 'O') { board[tmp.x][tmp.y] = 'B'; for (int[] dir : dirs) queue.offer(new Point(tmp.x + dir[0], tmp.y + dir[1])); } } } }
好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力。
