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

知识点

递归，dfs

解题思路

使用深度优先搜索 (DFS) 来查找与边界上的 ‘B’ 相连的所有 ‘B’。将边界上的 ‘B’ 标记为特殊字符 ‘#’。然后，遍历整个矩阵，将剩余的 ‘B’ 修改为 ‘A’，将特殊字符 ‘#’ 恢复为 ‘B’。最后返回修改后的矩阵。

Java题解

import java.util.*;


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

        int m = board.length;
        int n = board[0].length;

        // 将边界上与 'A' 相连的 'B' 标记为特殊字符 '#'
        for (int i = 0; i < m; i++) {
            if (board[i][0] == 'B') {
                dfs(board, i, 0);
            }
            if (board[i][n - 1] == 'B') {
                dfs(board, i, n - 1);
            }
        }

        for (int j = 0; j < n; j++) {
            if (board[0][j] == 'B') {
                dfs(board, 0, j);
            }
            if (board[m - 1][j] == 'B') {
                dfs(board, m - 1, j);
            }
        }

        // 将剩余的 'B' 修改为 'A'，将特殊字符 '#' 恢复为 'B'
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'B') {
                    board[i][j] = 'A';
                } else if (board[i][j] == '#') {
                    board[i][j] = 'B';
                }
            }
        }

        return board;
    }

// 使用深度优先搜索 (DFS) 标记与指定位置相连的 'B' 为特殊字符 '#'
    private void dfs(char[][] board, int x, int y) {
        int m = board.length;
        int n = board[0].length;

        if (x < 0 || x >= m || y < 0 || y >= n || board[x][y] != 'B') {
            return;
        }

        board[x][y] = '#';

        dfs(board, x - 1, y);
        dfs(board, x + 1, y);
        dfs(board, x, y - 1);
        dfs(board, x, y + 1);
    }
}