码疯窝

LeetCode 每日一题 — Surrounded Regions

2014/12/19 15:25:35    分类: 日志连载    0人评论 次浏览

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

算法分析: 题意为将被X 包围的O 全转为X. 一个很典型的 Flood Fill 算法. 此题要找出被包围的不好找, 需要遍历完才能知道.
但我们可以找出没被包围的, 因为4 条边所延伸出去的都是没有被包围的, 因此解法为顺着board 的4条边进行DFS 搜索, 并且标记为F, 事后再遍历所有节点, F 改为 O, O 改为 X.
于是很快写出DFS 的递归算法, 可惜的是在Java 和 Python 中却堆栈溢出了. 故而只能改用BFS 算法.

Java:

public class Solution {
    private int height = 0;
    private int width = 0;
    private char[][] board = null;
    
    private void fill(int y, int x) {
        int code = 0;
        LinkedList queue = new LinkedList();
        if (this.board[y][x] == 'O')
            this.board[y][x] = 'F';
        else 
            return;
        queue.offer(y * this.width + x);
        
        while (!queue.isEmpty()) {
            code = (int)queue.poll();
            x = code % this.width;
            y = code / this.width;

            if (y < this.height - 1 && this.board[y + 1][x] == 'O') {
                this.board[y + 1][x] = 'F';
                queue.offer((y + 1) * this.width + x);
            }
            if (y > 0 && this.board[y - 1][x] == 'O') {
                this.board[y - 1][x] = 'F';
                queue.offer((y - 1) * this.width + x);
            }
            if (x < this.width - 1 && this.board[y][x + 1] == 'O') {
                this.board[y][x + 1] = 'F';
                queue.offer(y * this.width + x + 1);
            }
            if (x > 0 && this.board[y][x - 1] == 'O') {
                this.board[y][x - 1] = 'F';
                queue.offer(y * this.width + x - 1);
            }
        }
    }
    
    public void solve(char[][] board) {
        if (board == null || board.length ==0 || board[0].length == 0)
            return;
        int y = board.length;
        int x = board[0].length;
        if (x <= 2 || y <= 2)
            return;
        this.board = board;
        this.width = x;
        this.height = y;
        while (--x >= 0) {
            this.fill(0, x);
            this.fill(this.height - 1, x);
        }
        while (--y >= 0) {
            this.fill(y, 0);
            this.fill(y, this.width - 1);
        }
        
        y = this.height;
        while(--y >= 0) {
            x = this.width;
            while(--x >= 0) {
                if (this.board[y][x] == 'F')
                    this.board[y][x] = 'O';
                else if (this.board[y][x] == 'O')
                    this.board[y][x] = 'X';
            }
        }
        
    }
}

C++:

 

Python:

class Solution:
    
    # @param board, a 2D array
    # Capture all regions by modifying the input board in-place.
    # Do not return any value.
    def solve(self, board):
        if (board == None):
            return
        if (len(board) <=2):
            return
        if (len(board[0]) <=2):
            return
        
        
        self.__height = len(board)
        self.__width = len(board[0])
        self.__board = board
        w = self.__width
        h = self.__height


        for y in range(h):
            self.fill(y, 0)
            self.fill(y, w - 1)
        for x in range(w):
            self.fill(0, x)
            self.fill(h - 1, x)

        for y in range(h):
            for x in range(w):
                if board[y][x] == 'F': 
                    board[y][x] = 'O'
                elif board[y][x] == 'O': 
                    board[y][x] = 'X'

    def fill(self, y, x):
        board = self.__board
        if (board[y][x] != 'O'):
            return
        
        h = self.__height
        w = self.__width
        dir = ((1,0),(-1,0),(0,1),(0,-1))
        board[y][x] = 'F'
        queue = [(y, x)]
        while (queue):
            y, x = queue.pop()
            for k in range(4):
                yy = y + dir[k][0]
                xx = x + dir[k][1]
                if 0 <= xx < w and 0 <= yy < h and board[yy][xx] == 'O':
                    board[yy][xx] = 'F'
                    queue.append((yy, xx))
                
        
继续查看有关 日志连载的文章

0个访客评论