Cod sursa(job #2708554)

Utilizator AACthAirinei Andrei Cristian AACth Data 18 februarie 2021 21:33:09
Problema Hashuri Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.02 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("padure.in");
ofstream g("padure.out");
//#define int long long
const int Max = 1e3 + 5;
void nos()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}
int n,m,xs,ys,xf,yf;
int a[Max][Max];
int cost[Max][Max];
void check_mat()
{
        for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
            cout<<cost[i][j]<<' ';
        cout<<'\n';
    }
}
void read()
{
    f>>n>>m>>xs>>ys>>xf>>yf;
   // cout<<"wtf"<<n<<' '<<m<<'\n';
    int i,j;
    for(i=1; i<=n; i++)
        for(j=1; j<=m; j++)
            f>>a[i][j];

}
void bordeaza()
{
    int i;
    int j;
    int maxx = max(n,m);
    for(i=0; i<=maxx+1; i++)
        a[0][i] = a[i][0] = a[i][m+1] = a[n+1][i] = -1;
    for(i=1; i<=n; i++)
        for(j=1; j<=m; j++)
            cost[i][j] = -1;
}

int dx[] = {1,0,-1,0};
int dy[] = {0,-1,0,1};
deque < pair < int, int > > c;
void parcurge()
{
    cost[xs][ys] = 0;
    c.push_front({xs,ys});
    while(!c.empty())
    {
        int x = c.front().first;
        int y = c.front().second;
       // cout<<x<<' '<<y<<'\n';
        c.pop_front();
        int z;
        for(z = 0 ; z <= 3; z++)
        {
            int newx = x + dx[z];
            int newy = y + dy[z];
            if(a[newx][newy]!=-1)
            {
                int new_cost = cost[x][y];
                if(a[x][y]!=a[newx][newy])
                    new_cost ++;
                if(cost[newx][newy] == -1 or new_cost < cost[newx][newy])
                {
                    cost[newx][newy] = new_cost;
                    if(a[x][y] == a[newx][newy])
                    c.push_front({newx,newy});
                    else
                    c.push_back({newx,newy});
                }
            }
        }
    }
}
void solve()
{
    bordeaza();
    parcurge();
//check_mat();


    g<<cost[xf][yf];
}
void restart()
{

}

int32_t main()
{
    nos();

    read();
    solve();
    restart();

    return 0;
}