abc

mail@pastecode.io avatar
unknown
c_cpp
2 years ago
1.8 kB
2
Indexable
#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;
}