Cod sursa(job #2820608)

Utilizator tomaionutIDorando tomaionut Data 20 decembrie 2021 22:07:17
Problema Car Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.69 kb
#include <bits/stdc++.h>
#define INF 1e9
using namespace std;
ifstream fin("car.in");
ofstream fout("car.out");
int a[10][10], n, m, xs, ys, xf, yf;
int c[505][505], d[8][505][505];
queue <pair < int, int > > Q;
int dx[] = { 1,1,0,-1,-1,-1,0,1 };
int dy[] = { 0,-1,-1,-1,0,1,1,1 };
bool OK(int i, int j)
{
    return (1 <= i and i <= n and 1 <= j and j <= m);
}
int main()
{
    int i, j, k, x, y, sol = -1, p;
    for (i = 0; i <= 7; i++)
        for (j = 0; j <= 7; j++)
            a[i][j] = abs(i - j);
    for (i = 0; i <= 7; i++)
        for (j = 0; j <= 7; j++)
            if (a[i][j] > 4) a[i][j] = 8 - a[i][j];
    fin >> n >> m >> xs >> ys >> xf >> yf;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
            fin >> c[i][j];
    for (i = 0; i <= 7; i++)
        for (j = 1; j <= n; j++)
            for (k = 1; k <= m; k++)
                d[i][j][k] = INF;

    for (i = 0; i <= 7; i++)
        d[i][xs][ys] = 0;

    Q.push({ xs,ys });
    while (!Q.empty())
    {
        x = Q.front().first;
        y = Q.front().second;
        Q.pop();
        for (k = 0; k <= 7; k++)
        {
            i = x + dx[k];
            j = y + dy[k];
            if (OK(i, j) and c[i][j] == 0)
                for (p = 0; p <= 7; p++)
                {
                    if (d[k][x][y] + a[p][k] < d[p][i][j])
                    {
                        d[p][i][j] = d[k][x][y] + a[p][k];
                        Q.push({ i,j });
                    }
                }
        }
    }
    sol = INT_MAX;
    for (i = 0; i <= 7; i++)
        if (d[i][xf][yf] != INF)
            sol = min(sol, d[i][xf][yf]);
    fout << sol;

    return 0;
}