飞地的数量

Leetcode题目链接

描述

详见中文题目链接。

解答

class Solution {
private:
    int m, n;
    int dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0};

    void dfs(vector<vector<int>>& grid, int x, int y) {
        if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] != 1) return;
        grid[x][y] = 0;
        for (int i = 0; i < 4; i++) {
            dfs(grid, x + dx[i], y + dy[i]);
        }
    }

public:
    int numEnclaves(vector<vector<int>>& grid) {
        m = grid.size(); n = grid[0].size();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || j == 0 || i == m - 1 || j == n - 1)
                    dfs(grid, i, j);
            }
        }
        return accumulate(begin(grid), end(grid), 0, [](int s, vector<int>& r) {
            return s + accumulate(begin(r), end(r), 0);
        });
    }
};