DFS: Connected Cell in a Grid

  • + 0 comments

    why do they want DFS? component size problems are more intuitively done with BFS.

    DFS recursive, not iterative:

    vector<int> S = {-1, 0, 1};
    
    void component(int i, int j, int n, int m, const vector<vector<int>>& grid, vector<vector<bool>>& visited, int& size) {
        visited[i][j] = true;
        ++size;
        for (int I : S) {
            for (int J : S) {
                if (i+I < 0 or i+I >= n or j+J < 0 or j+J >= m or visited[i+I][j+J] or grid[i+I][j+J] == 0) continue;
                component(i+I, j+J, n, m, grid, visited, size);
            }
        }
    }
    
    int maxRegion(int n, int m, const vector<vector<int>>& grid) {
        vector<int> components;
        vector<vector<bool>> visited(n, vector<bool>(m));
        int size = 0;
        for (int i=0; i < n; ++i) {
            for (int j=0; j < m; ++j) {
                if (visited[i][j] or grid[i][j] == 0) continue;
                size = 0;
                component(i, j, n, m, grid, visited, size);
                components.push_back(size);
            }
        }
        return *max_element(components.begin(), components.end());
    }
    
    int main()
    {
        int n, m, k;
        cin >> n >> m;
        vector<vector<int>> grid(n, vector<int>(m));
        for (int i=0; i < n; ++i) {
            for (int j=0; j < m; ++j) {
                cin >> k;
                grid[i][j] = k;
            }
        }
        cout << maxRegion(n, m, grid);
    }