Cod sursa(job #2667560)

Utilizator andrei.calin25Calin Andrei andrei.calin25 Data 3 noiembrie 2020 17:25:45
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.13 kb
#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
ifstream f("padure.in");
ofstream g("padure.out");

int n, m, padure[1001][1001], cost[1001][1001];
struct punct { int linie, coloana; }printul, castel;
queue<punct> coada;

void citire() {
    f>>n>>m;
    f>>printul.linie>>printul.coloana;
    f>>castel.linie>>castel.coloana;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++) {
            f>>padure[i][j];
            cost[i][j] = -1;
        }
}

void dfs(punct p, int c) {
    //cout<<"DFS-> "<<p.linie<<' '<<p.coloana<<" = "<<c<<endl;
    coada.push(p);
    cost[p.linie][p.coloana] = c;

    punct a1, a2, a3, a4;
    a1.linie = p.linie+1;
    a1.coloana = p.coloana;

    a2.linie = p.linie;
    a2.coloana = p.coloana+1;

    a3.linie = p.linie-1;
    a3.coloana = p.coloana;

    a4.linie = p.linie;
    a4.coloana = p.coloana-1;

    if(padure[p.linie][p.coloana] == padure[a1.linie][a1.coloana]
       && cost[a1.linie][a1.coloana] == -1)
    {
        cost[a1.linie][a1.coloana] = cost[p.linie][p.coloana];
        //cout<<"A ";

        dfs(a1, c);
    }

    if(padure[p.linie][p.coloana] == padure[a2.linie][a2.coloana]
       && cost[a2.linie][a2.coloana] == -1)
    {
        cost[a2.linie][a2.coloana] = cost[p.linie][p.coloana];
        //cout<<"B ";

        dfs(a2, c);
    }

    if(padure[p.linie][p.coloana] == padure[a3.linie][a3.coloana]
       && cost[a3.linie][a3.coloana] == -1)
    {
        cost[a3.linie][a3.coloana] = cost[p.linie][p.coloana];
        //cout<<"C ";

        dfs(a3, c);
    }

    if(padure[p.linie][p.coloana] == padure[a4.linie][a4.coloana]
       && cost[a4.linie][a4.coloana] == -1)
    {
        cost[a4.linie][a4.coloana] = cost[p.linie][p.coloana];
        //cout<<"D ";

        dfs(a4, c);
    }
}

void bfs(punct p) {

    dfs(p, 0);

    punct x;

    while(!coada.empty()) {

        //cout<<"\n: ";

        x = coada.front();
        coada.pop();

        //cout<<x.linie<<' '<<x.coloana<<' ';


        punct a1, a2, a3, a4;
        a1.linie = x.linie+1;
        a1.coloana = x.coloana;
        //cout<<"\n -> "<<a1.linie<<' '<<a1.coloana<<" = "<<cost[a1.linie][a1.coloana]<<endl;


        a2.linie = x.linie;
        a2.coloana = x.coloana+1;

        a3.linie = x.linie-1;
        a3.coloana = x.coloana;

        a4.linie = x.linie;
        a4.coloana = x.coloana-1;

        if(cost[a1.linie][a1.coloana] == -1)
            dfs(a1, cost[x.linie][x.coloana] + 1);

        if(cost[a2.linie][a2.coloana] == -1)
            dfs(a2, cost[x.linie][x.coloana] + 1);

        if(cost[a3.linie][a3.coloana] == -1)
            dfs(a3, cost[x.linie][x.coloana] + 1);

        if(cost[a4.linie][a4.coloana] == -1)
            dfs(a4, cost[x.linie][x.coloana] + 1);
    }
}

int main() {

    citire();

    bfs(printul);

//    cout<<endl;
//    for(int i=1; i<=n; i++){
//        for(int j=1; j<=m; j++)
//            cout<<cost[i][j]<<' ';
//        cout<<'\n';
//    }
//
//    cout<<"________________";
//    cout<<endl;
//    for(int i=1; i<=n; i++){
//        for(int j=1; j<=m; j++)
//            cout<<padure[i][j]<<' ';
//        cout<<'\n';
//    }

    g<<cost[castel.linie][castel.coloana];
}