07/29 23:39

# 题目：130. 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.

Example:

```X X X X
X O O X
X X O X
X O X X```

After running your function, the board should be:

```X X X X
X X X X
X X X X
X O X X```

Explanation:

Surrounded regions shouldn’t be on the border, which means that any `'O'` on the border of the board are not flipped to `'X'`. Any `'O'` that is not on the border and it is not connected to an `'O'` on the border will be flipped to `'X'`. Two cells are connected if they are adjacent cells connected horizontally or vertically.

# 解题思路

Traverse from the border to the inside and mark all the 'O's that are not surrounded by 'X' as 'V' (visited).

1. 从四条边上的O元素开始BFS，所有相连的O都赋个新值，比如‘Y’
2. 扫描整个数组，所有现存的O元素全部置为X，所有Y元素置为O

BFS (queue).

```X X X X
X X O X
X O X X
X O X X
```

```X X X X
X X O X
X Y X X
X Y X X
```

```X X X X
X X X X
X O X X
X O X X
```

# 最终实现

#### Java实现

``````import java.util.LinkedList;

// use BFS. The idea refers to https://wdxtub.com/interview/14520604919872.html
public class Solution {

public void solve(char[][] board) {
if (null == board) {
return;
}
if (board.length == 0) {
return;
}
printBoard(board);
processBorderRegions(board);
printBoard(board);
resetBoard(board);
printBoard(board);
}

private void processBorderRegions(char[][] board) {
int rowNum = board.length;
int colNum = board[0].length;
// Step 1. do with the top edge
for (int col = 0; col < colNum; col++) {
if (board[0][col] == 'O') {
bfsOnPosition(board, new Position(0, col));
}
}
// Step 2. do with the bottom edge
for (int col = 0; col < colNum; col++) {
if (board[rowNum-1][col] == 'O') {
bfsOnPosition(board, new Position(rowNum-1, col));
}
}
// Step 3. do with the left edge
for (int row = 0; row < rowNum; row++) {
if (board[row][0] == 'O') {
bfsOnPosition(board, new Position(row, 0));
}
}
// Step 4. do with the right edge
for (int row = 0; row < rowNum; row++) {
if (board[row][colNum-1] == 'O') {
bfsOnPosition(board, new Position(row, colNum-1));
}
}
}

private void bfsOnPosition(char[][] board, Position pos) {
board[pos.row][pos.col] = 'Y';
queue.push(pos.up());
queue.push(pos.down());
queue.push(pos.left());
queue.push(pos.right());
while(!queue.isEmpty()) {
pos = queue.poll();
if (pos.row < 0 || pos.row >= board.length || pos.col < 0 || pos.col >= board[0].length) {
continue;
}
if (board[pos.row][pos.col] == 'O') {
board[pos.row][pos.col] = 'Y';
queue.push(pos.up());
queue.push(pos.down());
queue.push(pos.left());
queue.push(pos.right());
}
}
}

private void resetBoard(char[][] 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';
} else if (board[i][j] == 'Y') {
board[i][j] = 'O';
}
}
}
}

private void printBoard(char[][] board) {
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
System.out.print(board[i][j]);
}
System.out.println();
}
System.out.println();
}

public static void main(String[] args) {
char[][] board = new char[4][4];
board[0][0] = 'X';
board[0][1] = 'X';
board[0][2] = 'X';
board[0][3] = 'X';
board[1][0] = 'X';
board[1][1] = 'X';
board[1][2] = 'O';
board[1][3] = 'X';
board[2][0] = 'X';
board[2][1] = 'O';
board[2][2] = 'X';
board[2][3] = 'X';
board[3][0] = 'X';
board[3][1] = 'O';
board[3][2] = 'X';
board[3][3] = 'X';
Solution solution = new Solution();
solution.solve(board);
}

class Position {
int row;
int col;

public Position(int row, int col) {
this.row = row;
this.col = col;
}

public int getCol() {
return col;
}

public int getRow() {
return row;
}

public void setCol(int col) {
this.col = col;
}

public void setRow(int row) {
this.row = row;
}

public Position up() {
return new Position(row-1, col);
}

public Position down() {
return new Position(row+1, col);
}

public Position left() {
return new Position(row, col-1);
}

public Position right() {
return new Position(row, col+1);
}
}

}
``````

0
0 收藏

0 评论
0 收藏
0