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

考察知识点：回溯

题目分析：

题目中其实已经给出思路。我们可以遍历边界，当遇到B字符时，就是递归的入口。递归时就找到与之相邻的没有被访问过的B字符位置即可。

我这里新建了一个全是A，大小与board相同的数组。当遇到满足条件的B字符时就修改res的值，res也能帮助判断一个位置是否被访问过。

所用编程语言：C++

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param board char字符型vector<vector<>> 
     * @return char字符型vector<vector<>>
     */
    void dfs(int i, int j, vector<vector<char>> &board, vector<vector<char>> &res) {
        res[i][j] = 'B';
        int dx[4] = {-1, 0, 1, 0};
        int dy[4] = {0, 1, 0, -1};
        int m = board.size();
        int n = board[0].size();

        if (i < 0 || i >= m || j < 0 || j >= n) return;
        for (int x = 0; x < 4; x++) {
            int row = i + dx[x];
            int col = j + dy[x];
            if (row >= 0 && row < m && col >= 0 && col < n && board[row][col] == 'B' && res[row][col] == 'A') {
                dfs(row, col, board, res);
            }
        }
    }
    vector<vector<char> > solve(vector<vector<char> >& board) {
        // write code here
        int m = board.size();
        int n = board[0].size();
        vector<vector<char>> res(m, vector<char>(n, 'A'));

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

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

        return res;
    }
};