Cod sursa(job #2925299)

Utilizator PetrescuAlexandru Petrescu Petrescu Data 13 octombrie 2022 22:34:30
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.84 kb
#include <bits/stdc++.h>

using namespace std;
const int NMAX = 1000;

struct Celula{
    int l, c, cap;

    Celula(int l, int c, int cap):l(l), c(c), cap(cap){}
    Celula(){}
};

int mat[NMAX + 5][NMAX + 5];
int viz[NMAX + 5][NMAX + 5];
int dirlin[] = {-1, 0, 1, 0}, dircol[] = {0, 1, 0, -1};

bool bfs(int n, int cap, int pl, int pc, int cl, int cc) {
    queue<Celula> Q;

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            viz[i][j] = -1;

    viz[pl][pc] = 1;

    Q.push(Celula(pl, pc, cap));

    while(!Q.empty()) {
        auto [l, c, cap] = Q.front();
        Q.pop();

        for(int dir = 0; dir < 4; dir++) {
            int newL = l + dirlin[dir];
            int newC = c + dircol[dir];

            if(newL > 0 && newL <= n && newC > 0 && newC <= n) {
                if(mat[l][c] != mat[newL][newC] && !cap)
                    continue;

                if(viz[newL][newC] < cap - (mat[l][c] != mat[newL][newC])) {
                    viz[newL][newC] = cap - (mat[l][c] != mat[newL][newC]);
                    if(newL == cl && newC == cc)
                        return true;

                    Q.push({newL, newC, cap - (mat[l][c] != mat[newL][newC])});
                }
            }
        }
    }

    return false;
}

int main()
{
    ifstream fin("padure.in");
    ofstream fout("padure.out");

    int n, m, pl, pc, cl, cc;

    fin >> n >> m >> pl >> pc >> cl >> cc;

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            fin >> mat[i][j];

    int st = 1, dr = NMAX * NMAX;

    while(st <= dr) {
        int mij = (st + dr) / 2;

        if(bfs(n, mij, pl, pc, cl, cc))
            dr = mij - 1;
        else
            st = mij + 1;
    }

    fout << st;

    fin.close();
    fout.close();

    return 0;
}