asb
unknown
c_cpp
3 years ago
1.3 kB
10
Indexable
// 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;
}Editor is loading...