Cod sursa(job #2434053)

Utilizator CharacterMeCharacter Me CharacterMe Data 30 iunie 2019 15:03:48
Problema Car Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.91 kb
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
int Ox[8]={-1, -1, 0, 1, 1, 1, 0, -1};
int Oy[8]={0, 1, 1, 1, 0, -1, -1, -1};
int N, M, i, j, k, Map[501][501], Dist[8][501][501];
pair<int, int> Start, Finish;
struct Str{
    int x, y, dir;
};
struct comp{
    bool operator()(Str X, Str Y){
        if(Dist[X.dir][X.x][X.y]>Dist[Y.dir][Y.x][Y.y]) return true;
        return false;
    }
};
priority_queue<Str, vector<Str>, comp> Q;
int main(){
    freopen("car.in", "r", stdin);
    freopen("car.out", "w", stdout);
    scanf("%d%d%d%d%d%d", &N, &M, &Start.first, &Start.second, &Finish.first, &Finish.second);
    for(i=1; i<=N; ++i)
        for(j=1; j<=M; ++j){
            scanf("%d", &Map[i][j]);
            Map[i][j]=-Map[i][j];
         }
    for(i=0; i<8; ++i){
        pair<int, int> P=Start;
        while(P.first>=1 && P.first<=N && P.second>=1 && P.second<=M){
            if(Map[P.first][P.second]==-1) break;
            Dist[i][P.first][P.second]=1;
            if(P!=Start)Q.push({P.first, P.second, i});
            P.first+=Ox[i];
            P.second+=Oy[i];
        }
    }
    while(!Q.empty()){
        Str S=Q.top(); Q.pop();
        int add=-1, cost=3;
        for(i=S.dir-2; i<=S.dir+2; ++i){
            if(i>=0)j=i%8;
            else j=(i+8)%8;
            if(i==S.dir+1) add=1;
            cost+=add;
            pair<int, int> P={S.x+Ox[j], S.y+Oy[j]};
            while(P.first>=1 && P.first<=N && P.second>=1 && P.second<=M && Map[P.first][P.second]!=-1){
                if(Dist[j][P.first][P.second]==0){
                    Dist[j][P.first][P.second]=Dist[S.dir][S.x][S.y]+cost;
                    if(P==Finish) {printf("%d", Dist[j][P.first][P.second]-1); return 0;}
                    Q.push({P.first, P.second, j});
                }
                P.first+=Ox[j]; P.second+=Oy[j];
            }
        }
    }
    return 0;
}