abc
unknown
c_cpp
2 years ago
1.8 kB
2
Indexable
Never
#include <iostream> #include <vector> #include <algorithm> #include <cmath> using namespace std; void dfs(vector<vector<int>> &graph, int row, int col) { int n = graph.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) { // dfs(graph, rowNew, colNew); // } // } int x = row; int y = col; for (int i = 0; i < n; ++i) { // for (int j = col; j < n; ++j) { // if (graph[i][j] == 1 && i != j) { // graph[i][j] = 0; // dfs(graph, j, i); // } else if (graph[i][j] == 1 && i == j) { // graph[i][j] = 0; // } // } if (graph[x][i] == 1 && x != i) { graph[x][i] = 0; dfs(graph, i, x); } else if (graph[x][i] == 1 && x == i) { graph[x][i] = 0; } } // return area; } int countArea(vector<vector<int>> &graph, int n) { int result = 0; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (graph[i][j] == 1) { result++; dfs(graph, i, j); break; } } } return result; } int main() { int n; cin >> n; vector<vector<int>> graph(n, vector<int>(n)); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { cin >> graph[i][j]; } } cout << countArea(graph, n); return 0; }