DFS: Connected Cell in a Grid

  • + 0 comments

    Simple C++ Solution

    #include <bits/stdc++.h>
    
    using namespace std;
    vector<vector<bool>> graph;
    int rows, cols, area;
    
    void trace(int r, int c) {
        if (r < 0 || r >= rows || c < 0 || c >= cols) return;
        if (!graph[r][c]) return;
        graph[r][c] = false;
        area++;
        for (int i: {r - 1, r, r + 1}) {
            for (int j: {c - 1, c, c + 1}) {
                trace(i, j);
            }
        }
    }
    
    int main() {
        cin >> rows >> cols;
        graph.resize(rows, vector<bool>(cols, false));
        for (int r = 0; r < rows; ++r) {
            for (int c = 0; c < cols; ++c) {
                char connected;
                cin >> connected;
                graph[r][c] = connected == '1';
            }
        }
        int ans = 0;
        for (int r = 0; r < rows; ++r) {
            for (int c = 0; c < cols; ++c) {
                area = 0;
                trace(r, c);
                ans = max(ans, area);
            }
        }
        cout << ans;
    }