Cod sursa(job #3168157)

Utilizator andreipirjol5Andrei Pirjol andreipirjol5 Data 11 noiembrie 2023 17:21:31
Problema Car Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.63 kb
#include <fstream>
#include <climits>
#include <queue>

using namespace std;
ifstream fin ("car.in");
ofstream fout ("car.out");

int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1}, dy[] = {0, 1, 1, 1, 0, -1, -1, -1};
const int INF = INT_MAX;
const int NMAX = 500;
int dp[NMAX + 5][NMAX + 5][10], a[NMAX + 5][NMAX + 5], n, m;

struct point
{
    int i, j, angle, cost;
};

queue <point> q, q1;

bool in (int x, int y)
{
    if(x >= 1 and x <= n + 1 and y >= 1 and y <= m + 1 and a[x][y] != 1)
            return true;

    return false;
}

void dijkstra()
{
    point node, neigh;
    while(!q.empty())
    {
        while(!q.empty())
        {
            node = q.front();
            q.pop();
            neigh.i = node.i + dx[node.angle];
            neigh.j = node.j + dy[node.angle];
            neigh.angle = node.angle;
            neigh.cost = node.cost;

            if(in(neigh.i, neigh.j) and dp[neigh.i][neigh.j][neigh.angle] > neigh.cost)
            {
                dp[neigh.i][neigh.j][neigh.angle] = neigh.cost;
                q.push(neigh);
            }

            neigh.cost++;
            neigh.angle = (neigh.angle + 1) % 8;
            neigh.i = node.i;
            neigh.j = node.j;

            if(in(neigh.i, neigh.j) and dp[neigh.i][neigh.j][neigh.angle] > neigh.cost)
            {
                dp[neigh.i][neigh.j][neigh.angle] = neigh.cost;
                q1.push(neigh);
            }

            neigh.angle = node.angle - 1;
            if(neigh.angle < 0)
                neigh.angle = 7;

            if(in(neigh.i, neigh.j) and dp[neigh.i][neigh.j][neigh.angle] > neigh.cost)
            {
                dp[neigh.i][neigh.j][neigh.angle] = neigh.cost;
                q1.push(neigh);
            }
        }

        while(!q1.empty())
        {
            q.push(q1.front());
            q1.pop();
        }
    }
}

int main()
{
    int x1, y1, x2, y2;
    fin >> n >> m >> x1 >> y1 >> x2 >> y2;

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            fin >> a[i][j];
            for(int k = 0; k < 8; k++)
                dp[i][j][k] = INF;
        }

    for(int k = 0; k < 8; k++)
    {
        point p;
        p.i = x1;
        p.j = y1;
        p.angle = k;
        p.cost = 0;
        q.push(p);
    }

    dijkstra();

    int ans = INF;

    //for(int i = 0; i < 8; i++)
        //fout << dp[x2][y2][i] << ' ';

    for(int i = 0; i < 8; i++)
        ans = min(ans, dp[x2][y2][i]);

    if(ans == INF)
        fout << -1;
    else fout << ans;

    fin.close();
    fout.close();
    return 0;
}