Cod sursa(job #2667207)

Utilizator vladdudauDudau Vlad vladdudau Data 3 noiembrie 2020 01:40:38
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.42 kb
#include<bits/stdc++.h>
#include<queue>

using namespace std;

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

const int dx[]={0,1,0,-1};
const int dy[]={1,0,-1,0};

struct punct
{
    int lin,col;
};

int M[1001][1001],MD[1001][1001];

queue <punct> q;

void DFS(punct x,int distanta)
{
    punct y;
    MD[x.lin][x.col]=distanta;
    q.push(x);

    for(int i=0;i<4;i++)
    {
        y.lin=x.lin+dx[i];
        y.col=x.col+dy[i];
        if(M[x.lin][x.col]==M[y.lin][y.col] && MD[y.lin][y.col]==0)
            DFS(y,distanta);
    }
}

void BFS(punct z)
{
    punct x,y;
    DFS(z,1);
    while(!q.empty())
    {
        x=q.front();
        q.pop();
        for(int i=0;i<4;i++)
        {
            y.lin=x.lin+dx[i];
            y.col=x.col+dy[i];
            if(MD[y.lin][y.col]==0)
            {
                DFS(y,1+MD[x.lin][x.col]);
            }
        }
    }
}


int main()
{
    int nrNod,nrMuchii;
    punct p,c;
    fin>>nrNod>>nrMuchii;
    fin>>p.lin>>p.col>>c.lin>>c.col;
    for(int i=1;i<=nrNod;i++)
        for(int j=1;j<=nrMuchii;j++)
            fin>>M[i][j];
    for(int j=1;j<=nrMuchii+1;j++)  ///Bordam
    {
        MD[0][j]=-1;
        MD[nrNod+1][j]=-1;
    }
    for(int i=1;i<=nrNod+1;i++)     ///Bordam
    {
        MD[i][0]=-1;
        MD[i][nrMuchii+1]=-1;
    }
    BFS(p);
    fout<<MD[c.lin][c.col]-1<<'\n';
    return 0;
}