asb
unknown
c_cpp
3 years ago
1.3 kB
6
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...