Cod sursa(job #2498049)

Utilizator victorzarzuZarzu Victor victorzarzu Data 23 noiembrie 2019 14:04:38
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.6 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("padure.in");
ofstream g("padure.out");
int n,m,xstart,ystart,xfinish,yfinish;
int a[1001][1001];
int drum[1001][1001];
bool viz[1001][1001];

struct Node
{
    int x;
    int y;
};

int x_path[] = {0,0,1,-1};
int y_path[] = {1,-1,0,0};

bool is_ok(int x,int y)
{
    return(x>=1 && y>=1 && x<=n && y<=m && viz[x][y] == false);
}


int Lee()
{
    deque<Node> dq;
    dq.push_back({xstart,ystart});
    viz[xstart][ystart] = true;
    drum[xstart][ystart] = 0;

    while(!dq.empty())
    {
        Node prim = dq.front();
        dq.pop_front();
        viz[prim.x][prim.y] = true;

        for(int k=0;k<4;++k)
        {
            int x_next = prim.x + x_path[k];
            int y_next = prim.y + y_path[k];
            if(is_ok(x_next,y_next))
            {
                if(a[x_next][y_next] == a[prim.x][prim.y])
                {
                    dq.push_front({x_next,y_next});
                    drum[x_next][y_next] = min(drum[prim.x][prim.y],drum[x_next][y_next]);
                }
                else
                {
                    dq.push_back({x_next,y_next});
                    drum[x_next][y_next] = min(drum[prim.x][prim.y] + 1, drum[x_next][y_next]);
                }
            }
        }
    }
}

int main()
{
    f>>n>>m>>xstart>>ystart>>xfinish>>yfinish;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            {
                f>>a[i][j];
                drum[i][j] = INFINITY;
            }
    Lee();
    g<<drum[xfinish][yfinish];
    return 0;
}