leetcode做题笔记130. 被围绕的区域

给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。

思路一：深度优先（DFS）

const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, 1, -1};
 
void solve(char** board, int boardSize, int* boardColSize) {
    int n = boardSize;
    if (n == 0) {
        return;
    }
    int m = boardColSize[0];
 
    int** que = (int**)malloc(sizeof(int*) * n * m);
    for (int i = 0; i < n * m; i++) {
        que[i] = (int*)malloc(sizeof(int) * 2);
    }
    int l = 0, r = 0;
    for (int i = 0; i < n; i++) {
        if (board[i][0] == 'O') {
            board[i][0] = 'A';
            que[r][0] = i, que[r++][1] = 0;
        }
        if (board[i][m - 1] == 'O') {
            board[i][m - 1] = 'A';
            que[r][0] = i, que[r++][1] = m - 1;
        }
    }
    for (int i = 1; i < m - 1; i++) {
        if (board[0][i] == 'O') {
            board[0][i] = 'A';
            que[r][0] = 0, que[r++][1] = i;
        }
        if (board[n - 1][i] == 'O') {
            board[n - 1][i] = 'A';
            que[r][0] = n - 1, que[r++][1] = i;
        }
    }
    while (l < r) {
        int x = que[l][0], y = que[l][1];
        l++;
        for (int i = 0; i < 4; i++) {
            int mx = x + dx[i], my = y + dy[i];
            if (mx < 0 || my < 0 || mx >= n || my >= m || board[mx][my] != 'O') {
                continue;
            }
            board[mx][my] = 'A';
            que[r][0] = mx, que[r++][1] = my;
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (board[i][j] == 'A') {
                board[i][j] = 'O';
            } else if (board[i][j] == 'O') {
                board[i][j] = 'X';
            }
        }
    }
    for (int i = 0; i < n * m; i++) {
        free(que[i]);
    }
    free(que);
}

分析：

本题若从内向外分析则难以判断是否需要将O替换为X，所以从外向内分析。从外向内分析时可考虑将最外层的O先替换为A，再判断内部O是否与A相邻，并设置方向数组方便判断方向，最后从外向内递归数组即可完成

总结：

本题考察对深度优先搜索的应用，分析出从外向内不断判断的方法，再将边界情况考虑清楚即可解决