Untitled

mail@pastecode.io avatar
unknown
plain_text
2 years ago
3.4 kB
5
Indexable
Never
#include <bits/stdc++.h>
using namespace std;

int main()
{
    // 8 nodes surrounding the cur node
    int a[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
    int b[8] = {-1, 0, 1, -1, 1, -1, 0, 1};

    int n, m;                  // total columns and rows of the matrix
    int i, j;                  // iterators
    int x, y;                  // indicate the pos. of a node
    int ct;                    // counter
    int **graph;               // store values of the input matrix
    bool **visited;            // check if a node is visited
    queue<vector<int>> q;      // queue for dfs
    vector<int> cur;           // current node
    map<int, vector<int>> res; // store the results

    cin >> n >> m;

    graph = new int *[m];
    visited = new bool *[m];

    // read the input
    for (i = 0; i < m; i++)
    {
        graph[i] = new int[n];
        visited[i] = new bool[n];

        for (j = 0; j < n; j++)
        {
            cin >> graph[i][j];

            if (res.find(graph[i][j]) == res.end())
            {
                vector<int> temp;
                res[graph[i][j]] = temp;
            }

            visited[i][j] = false;
        }
    }

    // traverse throught each node in graph
    for (i = 0; i < n * m; i++)
    {
        x = i % n;
        y = (i - x) / n;

        // skip if the node is visited
        if (visited[y][x])
        {
            continue;
        }

        // count the total connected nodes
        ct = 0;

        // set up the starting node
        if (i != 0)
        {
            cur.pop_back();
            cur.pop_back();
        }

        cur.push_back(x);
        cur.push_back(y);

        q.push(cur);

        while (!q.empty())
        {
            // get the cur node
            cur = q.front();
            q.pop();

            x = cur.at(0);
            y = cur.at(1);

            // skip visited node
            if (visited[y][x])
            {
                continue;
            }

            visited[y][x] = true; // set the cur node to visited
            ct++;                 // increase the counter

            // find all the connnected nodes w/ cur node
            for (j = 0; j < 8; j++)
            {
                int adjX = x + a[j];
                int adjY = y + b[j];

                // skip the visited/invalid ones
                if (adjX < 0 || adjX >= n || adjY < 0 || adjY >= m || visited[adjY][adjX] || graph[adjY][adjX] != graph[y][x])
                {
                    continue;
                }

                // else add the connected node to queue
                cur.pop_back();
                cur.pop_back();
                cur.push_back(adjX);
                cur.push_back(adjY);

                q.push(cur);
            }
        }

        // add the result to the result map
        res.find(graph[y][x])->second.push_back(ct);
    }

    // print the result
    for (map<int, vector<int>>::iterator itr = res.begin(); itr != res.end(); ++itr)
    {
        cout << itr->first << " :";

        sort(itr->second.begin(), itr->second.end()); // sort the vector
        for (i = 0; i < itr->second.size(); i++)
        {
            cout << " " << itr->second.at(i);
        }

        cout << "\n";
    }
}