Cod sursa(job #2905613)

Utilizator andreiiorgulescuandrei iorgulescu andreiiorgulescu Data 22 mai 2022 17:23:37
Problema Car Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in("car.in");
ofstream out("car.out");

int d[505][505][10],n,m,ls,cs,lf,cf;
int a[505][505];
queue<pair<pair<int,int>,int>>q;
int dl[] = {-1,-1,0,1,1,1,0,-1};
int dc[] = {0,1,1,1,0,-1,-1,-1};
bool is[505][505][10];

void lee()
{
    for (int i = 0; i < 8; i++)
        q.push({{ls,cs},i}),d[ls][cs][i] = 0;
    while (!q.empty())
    {
        pair<pair<int,int>,int>e = q.front();
        is[e.first.first][e.first.second][e.second] = false;
        q.pop();
        for (int i = 0; i <= 7; i++)
        {
            int lin = e.first.first + dl[i],col = e.first.second + dc[i];
            int dif = max(e.second,i) - min(e.second,i);
            if (dif >= 5)
                dif = 8 - dif;
            if (d[lin][col][i] > d[e.first.first][e.first.second][e.second] + dif and lin >= 1 and lin <= n and col >= 1 and col <= m and a[lin][col] == 1)
            {
                d[lin][col][i] = d[e.first.first][e.first.second][e.second] + dif;
                if (is[lin][col][i] == false)
                {
                    q.push({{lin,col},i});
                    is[lin][col][i] = true;
                }
            }
        }
    }
}

int main()
{
    for (int i = 1; i <= 500; i++)
        for (int j = 1; j <= 500; j++)
            for (int q = 1; q <= 10; q++)
                d[i][j][q] = 1e9;
    in >> n >> m >> ls >> cs >> lf >> cf;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            in >> a[i][j],a[i][j] = 1 - a[i][j];
    lee();
    int minim = 1e9;
    for (int i = 0; i < 8; i++)
        minim = min(minim,d[lf][cf][i]);
    if (minim == 1e9)
        out << -1;
    else
        out << minim;
    return 0;
}