asb

mail@pastecode.io avatar
unknown
c_cpp
2 years ago
1.3 kB
1
Indexable
Never
// Tham khao: https://www.tutorialcup.com/interview/graph/max-area-of-island.htm

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int dfs(vector<vector<int>>& graph, int row, int col) {
    int m = graph.size();
    int n = graph[0].size();

    int area = 1;
    graph[row][col] = 0;
    vector<int> direction = {-1, 0, 1, 0, -1};

    for (int i = 0; i < 4; ++ i) {
        int rowNew = row + direction[i];
        int colNew = col + direction[i + 1];

        if (rowNew >= 0 && rowNew < m && colNew >= 0 && colNew < n && graph[rowNew][colNew] == 1) {
            area += dfs(graph, rowNew, colNew);
        }
    }

    return area;
}

int maxArea(vector<vector<int>>& graph, int m, int n) {
    int result = 0;
    for (int i = 0; i < m; ++ i) {
        for (int j = 0; j < n; ++ j) {
            if (graph[i][j] == 1) {
                result = max(result, dfs(graph, i, j));
            }
        }
    }

    return result;
}



int main() {
    int m, n;
    cin >> m >> n;

    vector<vector<int>> graph(m, vector<int>(n));
    for (int i = 0; i < m; ++ i) {
        for (int j = 0; j < n; ++ j) {
            cin >> graph[i][j];
        }
    }

    cout << maxArea(graph, m, n);
    return 0;
}