`

LeetCode 130 - 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.

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

这个题目用到的方法是图形学中的一个常用方法:Flood fill算法,其实就是从一个点出发对周围区域进行目标颜色的填充。背后的思想就是把一个矩阵看成一个图的结构,每个点看成结点,而边则是他上下左右的相邻点,然后进行一次广度或者深度优先搜索。

 

这道题首先四个边缘上的‘O’点都不是被surrounded的,这是很直接能看出的,麻烦的是与这些边界上的‘O’点毗邻的其他‘O’点,这些点由于跟边缘上的'O'毗邻,所以也米有被‘X’包裹住。所以我们的想法是:把边界上的‘O’点都找出来,对它们做Flood Fill, 把联通的‘O’区域找出来,把这个区域的点统统由‘O’替换为其他字符比如‘$’。这样没有被替换仍旧为‘O’的那些点,就是被‘X’包裹的。这样整体扫描一次,剩下的所有'O'都应该被替换成'X',而'$'那些最终应该是还原成'O'。

 

复杂度分析上,我们先对边缘做Flood fill算法,因为只有是'O'才会进行,而且会被替换成'#',所以每个结点改变次数不会超过一次,因而是O(m*n)的复杂度,最后一次遍历同样是O(m*n),所以总的时间复杂度是O(m*n)。

 

空间上没懂,看了别人的思路。空间上就是递归栈(深度优先搜索)或者是队列(广度优先搜索)的空间,同时存在的空间占用不会超过O(m+n)(以广度优先搜索为例,每次队列中的结点虽然会往四个方向拓展,但是事实上这些结点会有很多重复,假设从中点出发,可以想象最大的扩展不会超过一个菱形,也就是n/2*2+m/2*2=m+n,所以算法的空间复杂度是O(m+n))

 

方法选择当然DFS和BFS都可以,DFS如果用递归来实现,像Flood Fill算法里那样,图形或者矩阵一般很大,递归容易导致堆栈溢出。所以即使用DFS,也要用Stack来写。

public void solve(char[][] board) {
    if(board==null||board.length==0||board[0].length==0) return;
    int m = board.length, n=board[0].length;
    for(int i=0; i<m; i++) {
        if(board[i][0] == 'O') bfs(board, i, 0);
        if(board[i][n-1] == 'O') bfs(board, i, n-1);
    }
    for(int j=0; j<n; j++) {
        if(board[0][j] == 'O') bfs(board, 0, j);
        if(board[m-1][j] == 'O') bfs(board, m-1, j);
    }
    for(int i=0; i<m; i++) {
        for(int j=0; j<n; j++) {
            if(board[i][j] == 'O') board[i][j] = 'X';
            else if(board[i][j] == '#') board[i][j] = 'O';
        }
    }
}

int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
private void bfs(char[][] board, int i, int j) {
    int m = board.length, n = board[0].length;
    Queue<Integer> q = new LinkedList<Integer>();
    q.offer(i*n+j);
    while(!q.isEmpty()) {
        int v = q.poll();
        int row = v/n;
        int col = v%n;
        board[row][col] = '#';
        for(int k=0; k<dir.length; k++) {
            int r = row + dir[k][0];
            int c = col + dir[k][1];
            if(r>=0 && r<m && c>=0 && c<n && board[r][c] == 'O') {
                q.offer(r*n+c);
                board[r][c] = '#';
            }
        }
    }
}

Reference:

http://www.cnblogs.com/EdwardLiu/p/4014864.html

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics