2014
10-13

# LeetCode-Surrounded Regions[BFS搜索Java&Python]

Surrounded Regions

Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

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

Java代码：

public class Solution {
public static void solve(char[][] board) {
if (board == null || board.length == 0)
return;
int m = board.length;
int n = board[0].length;
boolean visited[][] = new boolean[m][n];
int dir[][] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {

//以下是标准的BFS搜索，用visitedPoints记录访问的O
if (board[i][j] == 'O' && !visited[i][j]) {
boolean surounned = true;
List<Integer> visitedPoints = new ArrayList<Integer>();
visited[i][j] = true;
while (queue.size() > 0) {
int point = queue.poll();
int x = point/n;
int y = point%n;
for (int k = 0; k < 4; k++) {
int nextx = x + dir[k][0];
int nexty = y + dir[k][1];
if (nextx >= 0 && nextx < m && nexty >= 0 && nexty < n) {
if (board[nextx][nexty] == 'O' && !visited[nextx][nexty])
visited[nextx][nexty] = true;
} else {
surounned = false;
}
}
}

//如果当前遍历到的O是被包围的
if (surounned) {
for (int p : visitedPoints)
board[p / n][p % n] = 'X';
}
}
}
}
}
}

解法2

class Solution:
# @param board, a 9x9 2D array
# Capture all regions by modifying the input board in-place.
# Do not return any value.
def solve(self, board):
m = len(board)
if m <= 2 or board is None: return
n = len(board[0])
if n <= 2: return
dir = ((1,0),(-1,0),(0,1),(0,-1))

def bfs(x, y):
if board[x][y] != 'O': return
queue = [(x,y)]
board[x][y] = 'V'
while queue:
x,y = queue.pop()
for k in range(4):
nextx = x + dir[k][0]
nexty = y + dir[k][1]
if 0 <= nexty < n and 0 <= nextx < m and board[nextx][nexty] == 'O':
board[nextx][nexty] = 'V'
queue.append((nextx,nexty))

for i in range(m):
bfs(i,0); bfs(i,n-1) #只从边开始DFS
for i in range(n):
bfs(0,i); bfs(m-1,i)

for i in range(m):
for j in range(n):
if board[i][j] == 'V': board[i][j] = 'O'
elif board[i][j] == 'O': board[i][j] = 'X'

1. 样例输出和程序输出不吻合，修改一下样例输出吧。我用的是VC编译器，会提示我的i和j变量重复定义

2. A猴子认识的所有猴子和B猴子认识的所有猴子都能认识，这句话用《爱屋及乌》描述比较容易理解……