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

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param board char字符型二维数组
     * @return char字符型二维数组
     */
    public char[][] solve (char[][] board) {
        int m = board.length, n = board[0].length;
        int[][] dirs = new int[][] {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        boolean[][] flag = new boolean[m][n];
        Queue<int[]> queue = new ArrayDeque<>();
        for (int i = 0; i < m; i++) {
            if (board[i][0] == 'B') {
                queue.offer(new int[] {i, 0});
            }
            if (board[i][n - 1] == 'B') {
                queue.offer(new int[] {i, n - 1});
            }
        }
        for (int i = 0; i < n; i++) {
            if (board[0][i] == 'B') {
                queue.offer(new int[] {0, i});
            }
            if (board[m - 1][i] == 'B') {
                queue.offer(new int[] {m - 1, i});
            }
        }
        while (!queue.isEmpty()) {
            int[] poll = queue.poll();
            int x = poll[0], y = poll[1];
            flag[x][y] = true;
            for (int[] dir : dirs) {
                int nx = x + dir[0], ny = y + dir[1];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && !flag[nx][ny] &&
                        board[nx][ny] == 'B') {
                    queue.offer(new int[] {nx, ny});
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!flag[i][j] && board[i][j] == 'B') {
                    board[i][j] = 'A';
                }
            }
        }
        return board;
    }
}

知识点：

广度优先搜索

解题分析：

题目要求要将被包围的B转换为A，边界处不属于被包围的范围，故我们可以从边界出发，向内遍历所有的Ｂ并标记，表明被标记的Ｂ不会被转换成Ａ。具体来说，将四个边界的Ｂ入队，然后依次出队，向四个方向进行广度优先搜索，将其依次标记并入队，直至队列中没有剩余元素，也就标记了所有的与边界相通的Ｂ。

编程语言：

java