Cod sursa(job #2985004)

Utilizator robertanechita1Roberta Nechita robertanechita1 Data 25 februarie 2023 14:43:35
Problema Car Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.94 kb
#include <bits/stdc++.h>

using namespace std;

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

int n, m, a[505][505], dp[505][505][10];
///dp[i][j][d] costul minim pana la linia i, coloana j cu directia d
int x, y, xf, yf;
int dx[] = {1, 1, 0, -1, -1, -1,  0, 1};
int dy[] = {0, 1, 1,  1,  0, -1, -1,-1};
///drp, dr jos, jos, stg jos, stg, stg sus, sus, dr sus
///obs : nu vreau sa ajung la 135grade pt ca asta inseamna ca ma intorc
struct Elem{
    int i, j, k;
};
queue< Elem > q;

bool Check(int i, int j){
    return (i > 0 && i <= n && j > 0 && j <= m );
}

void Lee(int xs, int ys){
    int x, y, i, j, kP, d;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            for(int k = 0; k < 8; k++)
                dp[i][j][k] = 2e9;

    for(int k = 0; k < 8; k++){
        q.push({xs, ys, k});
        dp[xs][ys][k] = 0;
    }

    while(!q.empty()){
        i = q.front().i;
        j = q.front().j;
        kP = q.front().k;
        q.pop();
        for(int k = 0; k < 3; k++){
            d = (kP + k) % 8;
            x = i + dx[d];
            y = j + dy[d];
            if(Check(x, y) && a[x][y] == 0 && dp[x][y][d] > dp[i][j][kP] + k){
                dp[x][y][d] = dp[i][j][kP] + k;
                q.push({x, y, d});
            }
            d = (kP - k + 8) % 8;
            x = i + dx[d];
            y = j + dy[d];
            if(Check(x, y) && a[x][y] == 0 && dp[x][y][d] > dp[i][j][kP] + k){
                dp[x][y][d] = dp[i][j][kP] + k;
                q.push({x, y, d});
            }
        }
    }
}

int main()
{
    fin >> n >> m;
    fin >> x >> y >> xf >> yf;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            fin >> a[i][j];
    Lee(x, y);
    int ans = 2e9;
    for(int k = 0; k < 8; k++)
        ans = min(ans, dp[xf][yf][k]);
    if(ans == 2e9)
        fout << "-1\n";
    else
        fout << ans << "\n";
    return 0;
}