Cod sursa(job #2436703)

Utilizator CharacterMeCharacter Me CharacterMe Data 6 iulie 2019 19:03:58
Problema Car Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.99 kb
#include <iostream>
#include <cstdio>
#include <queue>
#define inf 1000001
#define x first
#define y second
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, area[501][501], solution[501][501][8];
pair<int, int> start, finish;
struct dot{
    int x, y, d;
};
queue<dot> q, next_q;
int main(){
    freopen("car.in", "r", stdin);
    freopen("car.out", "w", stdout);
    scanf("%d%d%d%d%d%d", &N, &M, &start.x, &start.y, &finish.x, &finish.y);
    for(i=1; i<=N; ++i)
    for(j=1; j<=M; ++j){
        scanf("%d", &area[i][j]);
        area[i][j]=1-area[i][j];
        for(k=0; k<8; ++k) solution[i][j][k]=inf;
    }
    for(i=0; i<8; ++i){
        solution[start.x][start.y][i]=1;
        q.push({start.x, start.y, i});
    }
    while(!q.empty()){
        while(!q.empty()){
            dot pos=q.front(), nbr; q.pop();
            if(pos.x==finish.x && pos.y==finish.y) {printf("%d", solution[pos.x][pos.y][pos.d]-1); return 0;}
            nbr=pos; nbr.x+=Ox[nbr.d]; nbr.y+=Oy[nbr.d];
            if(area[nbr.x][nbr.y]==1 && solution[pos.x][pos.y][pos.d]<solution[nbr.x][nbr.y][nbr.d]){
                q.push(nbr);
                solution[nbr.x][nbr.y][nbr.d]=solution[pos.x][pos.y][pos.d];
            }
            nbr=pos; nbr.d=(nbr.d+1)%8;
            if(area[nbr.x][nbr.y]==1 && solution[pos.x][pos.y][pos.d]+1<solution[nbr.x][nbr.y][nbr.d]){
                next_q.push(nbr);
                solution[nbr.x][nbr.y][nbr.d]=solution[pos.x][pos.y][pos.d]+1;
            }
            nbr=pos; --nbr.d; if(nbr.d==-1) nbr.d=7;
            if(area[nbr.x][nbr.y]==1 && solution[pos.x][pos.y][pos.d]+1<solution[nbr.x][nbr.y][nbr.d]){
                next_q.push(nbr);
                solution[nbr.x][nbr.y][nbr.d]=solution[pos.x][pos.y][pos.d]+1;
            }
        }
        while(!next_q.empty()){
            q.push(next_q.front());
            next_q.pop();
        }
    }
    printf("-1");
    return 0;
}