leetcode: 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

原问题链接：https://leetcode.com/problems/surrounded-regions/

 

问题分析

　　从问题描述中给定的条件来说，一开始有点难以找到一个解决的入口。对于矩阵中一个或者若干个被X字符包围的O字符，我们就需要找到一个方法来确定这些O字符是否确实被包围，而不是它们有连接的O字符出口。那么该怎么确定它有O字符的出口呢？从前面问题的描述里已经看到了，如果有O字符在矩阵的４个边上，如果我们有字符和这些字符相邻，那么就可以确定这些字符是和出口想通的，也就是说它们不可能被X字符包围。

　　现在问题就在于该怎么找到所有和这些出口字符相邻的字符呢？这就相当于一个动态扩展的过程了。如果我们碰到某个在出口的O字符，我们就需要去看它的周边的字符，如果有字符也是O，那么我们就要想办法标记这个字符，而且这个字符也将作为出口的一个连接，我们应该将这个字符的周边字符的情况继续考虑在内。按照这个过程，这就是一个图的遍历过程。我们可以考虑采用深度优先或者广度优先的方式来遍历。

　　既然我们访问过这些连接到出口的元素，我们就需要对它们做一个标记，防止它们被重复访问。在这里，我们可以采用将这些连接到出口的元素设置为另外一个特殊值的方式。这样在后面的访问里将它们重新设置成O就可以了。

　　从实现的角度来说，如果我们采用广度优先遍历的方式来处理，我们就需要一个队列，队列里应该记录我们当前访问的矩阵位置。该用什么来记录矩阵的位置呢？在java里对键值对类型的支持不太理想，我们可以引用AbstractMap.SimpleEntry这个类型。在最开始的时候我们程序遍历矩阵的４个边，将所有为O的元素加入到队列中，并将该位置的元素设置成别的值。剩下的就是用广度优先遍历不断的判断和加入新的符合条件的元素。

　　在遍历完之后，我们再遍历一遍矩阵，将设置成这个特殊值的元素设置回去，同时将找到的O元素设置为X，因为这些元素既然不能找到出口，肯定就可以被设置成X了。

　　按照这个思路，可以得到详细的代码实现如下：

 

import static java.util.AbstractMap.SimpleEntry;

public class Solution {
    public void solve(char[][] board) {
        if(board == null || board.length == 0 || board[0].length == 0) return;
        int m = board.length, n = board[0].length;
        Queue<SimpleEntry<Integer, Integer>> queue = new LinkedList<>();
        for(int i = 0; i < m; i++) {
            if(board[i][0] == 'O') {
                board[i][0] = 'A';
                queue.add(new SimpleEntry<>(i, 0));
            }
            if(board[i][n - 1] == 'O') {
                board[i][n - 1] = 'A';
                queue.add(new SimpleEntry<>(i, n - 1));
            }
        }
        for(int i = 0; i < n; i++) {
            if(board[0][i] == 'O') {
                board[0][i] = 'A';
                queue.add(new SimpleEntry<>(0, i));
            }
            if(board[m - 1][i] == 'O') {
                board[m - 1][i] = 'A';
                queue.add(new SimpleEntry<>(m - 1, i));
            }
        }
        while(!queue.isEmpty()) {
            SimpleEntry<Integer, Integer> entry = queue.remove();
            int row = entry.getKey();
            int col = entry.getValue();
            addEntry(board, row - 1, col, queue);
            addEntry(board, row + 1, col, queue);
            addEntry(board, row, col - 1, queue);
            addEntry(board, row, col + 1, queue);
        }
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(board[i][j] == 'A') board[i][j] = 'O';
                else if(board[i][j] == 'O') board[i][j] = 'X';
            }
        }
    }
    
    private void addEntry(char[][] board, int row, int col, Queue<SimpleEntry<Integer, Integer>> queue) {
        if(inRange(row, col, board) && board[row][col] == 'O') {
            board[row][col] = 'A';
            queue.add(new SimpleEntry<>(row, col));
        }
    }
    
    private boolean inRange(int row, int col, char[][] board) {
        return row >= 0 && row < board.length && col >= 0 && col < board[0].length;
    }
}