Alibi

My Life is Getting Better

Leetcode[130] Surrounded Regions

10 Nov 2015

###Task1 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.

For 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

###Python

class Solution(object):
    def solve(self, board):
        if len(board) == 0 or len(board[0]) == 0: # This is sooooo keng
            return
        M = len(board)
        N = len(board[0])
        for i in range(M):
            for j in range(N):
                if i == 0 or i == M-1 or j == 0 or j == N-1:
                    self.findAll(board, i, j)
        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'
        
    def findAll(self, board, row, col):
        if (board[row][col] != 'O'):
            return
        q = []
        q.append((row, col))
        while len(q) > 0:
            r, c = q.pop(0)
            if r < 0 or r >= len(board) or c < 0 or c >= len(board[0]):
                continue
            if board[r][c] != 'O':
                continue
            board[r][c] = 'V'
            q.append((r-1, c))
            q.append((r+1, c))
            q.append((r, c-1))
            q.append((r, c+1))

###Java

//BFS

public class Solution {

    public Queue<Integer> queue = new LinkedList<Integer>();

    public void enqueue(char[][] board, int i, int j, int row, int col) {
        if (i < 0 || i >= row || j < 0 || j >= col || board[i][j] != 'O') {
            return;
        }
        queue.offer(i * col + j);
        board[i][j] = '#';
    }

    public void merge(char[][] board, int i, int j, int row, int col) {

        enqueue(board, i, j, row, col);

        while (!queue.isEmpty()) {
            int crt = queue.poll();
            int r = crt / col;
            int c = crt % col;

            enqueue(board, r + 1, c, row, col);
            enqueue(board, r - 1, c, row, col);
            enqueue(board, r, c + 1, row, col);
            enqueue(board, r, c - 1, row, col);

        }

        return;
    }

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

        int row = board.length;
        int col = board[0].length;

        if (row <= 2 || col <= 2) {
        	return;
        }

        //merge the edge inside, from left/right
        for (int i = 0; i < row; i++) {
            merge(board, i, 0, row, col);
            merge(board, i, col - 1, row, col);
        }
        //merge from top/bottom
        for (int i = 0; i < col; i++) {
            merge(board, 0, i, row, col);
            merge(board, row - 1, i, row, col);
        }



        for (int i = 0; i < row; i++) {
        	for (int j = 0; j < col; j++) {
        		if (board[i][j] == '#') {
        			board[i][j] = 'O';
        		} else if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
        	}
        }

        return;
    }
}

###Points

每个结点改变次数不会超过一次，因而是O(mn)的复杂度，最后一次遍历同样是O(mn)，所以总的时间复杂度是O(mn)。空间上就是递归栈（深度优先搜索）或者是队列（广度优先搜索）的空间，同时存在的空间占用不会超过O(m+n)（以广度优先搜索为例，每次队列中的结点虽然会往四个方向拓展，但是事实上这些结点会有很多重复，假设从中点出发，可以想象最大的扩展不会超过一个菱形，也就是n/22+m/2*2=m+n，所以算法的空间复杂度是O(m+n)）

Related Posts