leetcode 130. Surrounded Regions（被围绕的区域）

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

 

一、问题描述

给定一个元素均为'O'和'X'的二维数组，将内部的'O'重置为'X'，边界上的'O'保持不变。

 

测试用例：

Input： X X X X X O O X X X O X X O X X Output： X X X X X X X X X X X X X O X X

 

二、代码实现

首先，遍历四条边界，如果当前元素是'X'，直接continue；如果当前元素是'O'，则将其置为'A'（标记），并且将与它相邻的所有'O'也置为'A'。

然后，两层循环遍历数组，将'O'置为'X'，将'A'恢复为'O'。

class Solution { public void solve(char[][] board) { if (board == null || board.length <= 2) { return; } //记住左右边界的'O' for (int i=0; i<board.length; i++) { dfs(board, i, 0); dfs(board, i, board[0].length-1); } //记住上下边界的'O' for (int j=1; j<board[0].length; j++) { dfs(board, 0, j); dfs(board, board.length-1, j); } //将内部的'O'置为'X'，同时将边界的'O'还原 for (int i=0; i<board.length; i++) { for (int j=0; j<board[0].length; j++) { if (board[i][j] == 'A') { board[i][j] = 'O'; } else if (board[i][j] == 'O') { board[i][j] = 'X'; } } } } private void dfs(char[][] board, int i, int j) { if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] == 'X') { return; } board[i][j] = 'A'; if (i-1 >= 0 && board[i-1][j] == 'O') { //上 这里的边界判断其实可以去掉 dfs(board, i-1, j); } if (i+1 < board.length && board[i+1][j] == 'O') { //下 dfs(board, i+1, j); } if (j-1 >= 0 && board[i][j-1] == 'O') { //左 dfs(board, i, j-1); } if (j+1 < board[0].length && board[i][j+1] == 'O') { //右 dfs(board, i, j+1); } } }