Cod sursa(job #2542727)

Utilizator NoemikulcsarKulcsar Noemi Noemikulcsar Data 10 februarie 2020 15:45:05
Problema Grigo Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <iostream>
#include <fstream>
#include <deque>

using namespace std;

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

int a[1005][1005], d[1005][1005], dx[6], dy[6];
deque <int> x;
deque <int> y;

int main()
{
    dx[1] = -1; dx[2] = 0; dx[3] = 1; dx[4] = 0;
    dy[1] = 0; dy[2] = -1; dy[3] = 0; dy[4] = 1;
    int n, m, xi, yi, xf, yf;
    fin >> n >> m >> xi >> yi >> xf >> yf;
    for (int i = 1; i <= n; i++)
        for (int j = 1;j <= m; j++)
            fin >> a[i][j];
    x.push_front(xi);
    y.push_front(yi);
    d[xi][yi] = 1;
    while (!x.empty())
    {
        int xret = x.front(), yret = y.front();
        x.pop_front();
        y.pop_front();
        for (int i = 1; i <= 4; i++)
        {
            int xx = xret + dx[i], yy = yret + dy[i];
            if (xx >= 1 && xx <= n && yy >= 1 && yy <= m)
            {
                if (a[xx][yy] == a[xret][yret])
                {
                    if (d[xret][yret] < d[xx][yy] || d[xx][yy] == 0)
                    {
                        d[xx][yy] = d[xret][yret];
                        x.push_front(xx);
                        y.push_front(yy);
                    }
                }
                else
                {
                    if (d[xret][yret] + 1 < d[xx][yy] || d[xx][yy] == 0)
                    {
                        d[xx][yy] = d[xret][yret] + 1;
                        x.push_back(xx);
                        y.push_back(yy);
                    }
                }
            }
        }
    }
    fout << d[xf][yf] - 1 << '\n';
    return 0;
}