Surrounded Regions

Java

class Solution {
		public void solve(char[][] board) {
				if (board == null || board.length == 0) return;
		int m = board.length;
				int n = board[0].length;
		
				for (int i = 0; i < m; i++) {
					bfs(board, i, 0);
					bfs(board, i, n - 1);
				}
				for (int j = 0; j < n; j++) {
					bfs(board, 0, j);
					bfs(board, m - 1, j);   //对边所有节点做bfs，在bfs中处理不是‘O' 的点
				}
				for (int i = 0; i < m; i++) {
					for (int j = 0; j < n; j++) {
						if (board[i][j] == 'W') {
							board[i][j] = 'O';
						} else {
							board[i][j] = 'X';
						}
					}
				}
		}

		private void bfs(char[][] board, int sx, int sy) {
			if (board[sx][sy] != 'O') {
				return;
			}
		
		int[] dx = {0, 0, 1, -1};
			int[] dy = {1, -1, 0, 0};
			Queue<Integer> qx = new LinkedList<>();
			Queue<Integer> qy = new LinkedList<>();
		
			qx.offer(sx);
			qy.offer(sy);
			board[sx][sy] = 'W';
			while (!qx.isEmpty()) {
				int cx = qx.poll();
				int cy = qy.poll();
				for (int i = 0; i < 4; i++) {
					int nx = cx + dx[i];
					int ny = cy + dy[i];
					if (nx >= 0 && nx < board.length && ny >= 0 && ny < board[0].length && board[nx][ny] == 'O') {
						board[nx][ny] = 'W';
						qx.offer(nx);
						qy.offer(ny);
					}
				}
			}
		}
}