You are viewing a single comment's thread. Return to all comments →
why do they want DFS? component size problems are more intuitively done with BFS.
DFS recursive, not iterative:
vector<int> S = {-1, 0, 1}; void component(int i, int j, int n, int m, const vector<vector<int>>& grid, vector<vector<bool>>& visited, int& size) { visited[i][j] = true; ++size; for (int I : S) { for (int J : S) { if (i+I < 0 or i+I >= n or j+J < 0 or j+J >= m or visited[i+I][j+J] or grid[i+I][j+J] == 0) continue; component(i+I, j+J, n, m, grid, visited, size); } } } int maxRegion(int n, int m, const vector<vector<int>>& grid) { vector<int> components; vector<vector<bool>> visited(n, vector<bool>(m)); int size = 0; for (int i=0; i < n; ++i) { for (int j=0; j < m; ++j) { if (visited[i][j] or grid[i][j] == 0) continue; size = 0; component(i, j, n, m, grid, visited, size); components.push_back(size); } } return *max_element(components.begin(), components.end()); } int main() { int n, m, k; cin >> n >> m; vector<vector<int>> grid(n, vector<int>(m)); for (int i=0; i < n; ++i) { for (int j=0; j < m; ++j) { cin >> k; grid[i][j] = k; } } cout << maxRegion(n, m, grid); }
Seems like cookies are disabled on this browser, please enable them to open this website
DFS: Connected Cell in a Grid
You are viewing a single comment's thread. Return to all comments →
why do they want DFS? component size problems are more intuitively done with BFS.
DFS recursive, not iterative: