LeetCode 130 Surrounded Regions

思路

bfs搜索，从四周开始灌水，寻找不被x包围的区域，先替换成W。最后再将O换成X， W换成O即可。该题主要是看代码的实现过程和bfs灌水的思想。
【注意输入为二维数组的题目中，对于x和y的定义，一般是x对应row，y对应col】

代码

public class Solution {
    /** @param board: board a 2D board containing 'X' and 'O'* @return: nothing*/public void surroundedRegions(char[][] board) {
    // write your code hereif(board == null || board.length == 0 || board[0].length == 0)return;int row = board.length;int col = board[0].length;for(int i = 0; i < row; i++) {
    bfs(board, i, 0);bfs(board, i, col - 1);}for(int i = 0; i < col; i++) {
    bfs(board, 0, i);bfs(board, row - 1, i);}for(int i = 0; i < row; i++) {
    for(int j = 0; j < col; j++) {
    if(board[i][j] == 'W') {
    board[i][j] = 'O';} else {
    board[i][j] = 'X';}}}}public void bfs(char[][] board, int sx, int sy) {
    // sx: start_point_x, row// sy: start_point_y, colif(board[sx][sy] != 'O') return;int row = board.length, col = board[0].length;Queue<Integer> qx = new LinkedList<>();Queue<Integer> qy = new LinkedList<>();int[] dx = {
    0, 0, 1, -1};int[] dy = {
    1, -1, 0, 0};qx.offer(sx);qy.offer(sy);board[sx][sy] = 'W'; // 'W' = Waterwhile(!qx.isEmpty()) {
    int cx = qx.poll(), cy = qy.poll();for(int i = 0; i < 4; i++) {
    int nx = cx + dx[i];int ny = cy + dy[i];if(0 <= nx && nx < row && 0 <= ny && ny < col && board[nx][ny] == 'O') {
    qx.offer(nx);qy.offer(ny);board[nx][ny] = 'W';}}}}
}

复杂度

时间复杂度O($n^2$), 空间复杂度O(1)