Cod sursa(job #2959642)

Utilizator user12345user user user user12345 Data 1 ianuarie 2023 21:54:54
Problema Matrice 2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.57 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

ifstream fin("matrice2.in");
ofstream fout("matrice2.out");

#define swich(i, j) n * (i - 1) + j
int t[90001], n, q, rez[20001], mat[301][301];
pair <int, int> Begin[20001];
pair <int, int> End[20001];

struct nod{
    int i, j, val;

    bool operator < (const nod& aux) const
    {
        return val > aux.val;
    }
} a[90001];
int sz; // a size

int root(int x)
{
    if (t[x] == x)
        return x;
    return t[x] = root(t[x]);
}

int d1[] = {0, -1, 0, 1, 0};
int d2[] = {0, 0, 1, 0, -1};

int main()
{
    fin >> n >> q;

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            fin >> mat[i][j];
            a[++sz] = {i, j, mat[i][j]};

            t[swich(i, j)] = swich(i, j);
        }
    }

    sort(a + 1, a + sz + 1);

    for (int i = 1; i <= q; i++)
        fin >> Begin[i].first >> Begin[i].second >> End[i].first >> End[i].second;

    int i = 1, x, y, c, r1, r2;

    while (i <= sz)
    {
        c = a[i].val; // iteration constant

        while (i <= sz && a[i].val == c)
        {
            r1 = root(swich(a[i].i, a[i].j));

            for (int k = 1; k <= 4; k++)
            {
                x = a[i].i + d1[k];
                y = a[i].j + d2[k];

                if (x < 0 || x > n || y < 0 || y > n || mat[x][y] < a[i].val)
                    continue;

                r2 = root(swich(x, y));
                t[r2] = r1;
            }

            i++;
        }

    }



    return 0;
}