题解 | #牛群的活动区域#

知识点：dfs

思路：我们使用二维布尔数组来记录位置是否已经被访问过。我们遍历每个边界的 ‘B’，然后从这些位置开始进行深度优先搜索，将所有与边界上的 ‘B’ 相连的 ‘B’ 标记为已访问。最后，我们再遍历整个矩阵，将未被访问的位置标记为 ‘A’。

编程语言：java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param board char字符型二维数组
     * @return char字符型二维数组
     */
    int[] dx = {-1, 0, 1, 0};
    int[] dy = {0, -1, 0, 1};
    public char[][] solve(char[][] board) {
        int n = board.length;
        int m = board[0].length;
        boolean[][] st = new boolean[n][m];

        for (int i = 0; i < n; i++) {
            if (!st[i][0] && board[i][0] == 'B') {
                st[i][0] = true;
                dfs(i, 0, n, m, board, st);
            }
            if (!st[i][m - 1] && board[i][m - 1] == 'B') {
                st[i][m - 1] = true;
                dfs(i, m - 1, n, m, board, st);
            }
        }

        for (int i = 0; i < m; i++) {
            if (!st[0][i] && board[0][i] == 'B') {
                st[0][i] = true;
                dfs(0, i, n, m, board, st);
            }
            if (!st[n - 1][i] && board[n - 1][i] == 'B') {
                st[n - 1][i] = true;
                dfs(n - 1, i, n, m, board, st);
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == 'A') continue;
                if (!st[i][j]) board[i][j] = 'A';
            }
        }

        return board;
    }

    private void dfs(int x, int y, int n, int m, char[][] board, boolean[][] st) {
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && !st[nx][ny] &&
                    board[nx][ny] == 'B') {
                st[nx][ny] = true;
                dfs(nx, ny, n, m, board, st);
            }
        }
    }
}