# asb

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;
}```