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

本题思路：从四条边上为'O'的点开始遍历(BFS/DFS)字符为‘O’的点，被遍历到的'O'点均为未被'X'包围的点，其余'O'点需要被替换为'X'。

但是使用DFS进行遍历的话，在测试时，会出现StackOverflow，只好采用BFS。

代码

import java.util.LinkedList;
import java.util.Queue;

public class SurroundedRegions {
	class Pair {
		int i;
		int j;

		Pair(int i, int j) {
			this.i = i;
			this.j = j;
		}
	}

	private int M;
	private int N;

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

		this.M = board.length;
		this.N = board[0].length;
		Queue
  
    queue = new LinkedList
   
    (); for (int i = 0; i < M; ++i) { if (board[i][0] == 'O') { queue.add(new Pair(i, 0)); bfs(queue, board); } if (board[i][N - 1] == 'O') { queue.add(new Pair(i, N - 1)); bfs(queue, board); } } for (int j = 1; j < N - 1; ++j) { if (board[0][j] == 'O') { queue.add(new Pair(0, j)); bfs(queue, board); } if (board[M - 1][j] == 'O') { queue.add(new Pair(M - 1, j)); bfs(queue, board); } } 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'; } } } } private void bfs(Queue
    
      queue, char[][] board) { while (!queue.isEmpty()) { Pair pair = queue.poll(); int i = pair.i; int j = pair.j; if (i < 0 || i >= M || j < 0 || j >= N || board[i][j] != 'O') { continue; } board[i][j] = '#'; queue.add(new Pair(i - 1, j)); queue.add(new Pair(i + 1, j)); queue.add(new Pair(i, j - 1)); queue.add(new Pair(i, j + 1)); } } }