首页 > 搜索 > BFS搜索 > LeetCode-Surrounded Regions[BFS搜索Java&Python]
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

分析:

典型的BFS题目。遍历每个字符,如果是“O”,则从当前字符开始BFS遍历,如果周围也是“O”则加入当前遍历的队列,知道遍历完所有相邻的“O”,于此同时,判断每个O是否是被包围的,只有由一个O是没有被包围的,则当前遍历的O的集合都是没有被包围的,因为这些O都是相连的。

当然,此题使用DFS也可以,只是测试数据过大,提交时StackOverFlow.

Java代码:

public class Solution {
public static void solve(char[][] board) {
		Queue<Integer> queue = new LinkedList<Integer>();
		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>();
					queue.add(i * n + j);
					visited[i][j] = true;
					while (queue.size() > 0) {
						int point = queue.poll();
						visitedPoints.add(point);
						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])
									queue.add(nextx * n + nexty);
								visited[nextx][nexty] = true;
							} else {
								surounned = false;
							}
						}
					}

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

 解法2

可以从边开始遍历BFS(DFS会栈溢出)遍历,把遍历到的点置为’V',表示访问过的,这样遍历的点都是没有被包围的。然后把剩下的那些O置为’V'即可.

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猴子认识的所有猴子都能认识,这句话用《爱屋及乌》描述比较容易理解……