Cod sursa(job #2638625)

Utilizator PatrickCplusplusPatrick Kristian Ondreovici PatrickCplusplus Data 29 iulie 2020 10:38:47
Problema Car Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.72 kb
#include <fstream>
#include <deque>
#include <iostream>
using namespace std;
ifstream fin("car.in");
ofstream fout("car.out");
int n, m, xi, yi, xf, yf, matrix[505][505], lung[505][505][8];
int dx[] = {-1,-1,0,1,1,1,0,-1};
int dy[] = {0,1,1,1,0,-1,-1,-1};
struct triplet{
    int x, y, dir;
};
deque <triplet> coada;
bool Valid(int i, int j, int dir){
    return i >= 1 && j >= 1 && i <= n && j <= m && matrix[i][j] == 0;
}
int main(){
    fin >> n >> m >> xi >> yi >> xf >> yf;
    for (int i = 1; i <= n; ++i){
        for (int j = 1; j <= m; ++j){
            fin >> matrix[i][j];
            for (int k = 0; k < 8; ++k){
                lung[i][j][k] = 1e9;
            }
        }
    }
    for (int k = 0; k < 8; ++k){
        lung[xi][yi][k] = 1;
        coada.push_front({xi, yi, k});
    }
    while (!coada.empty()){
        int x = coada.front().x, y = coada.front().y, dir = coada.front().dir;
        if (x == xf && y == yf){
            fout << lung[x][y][dir] - 1;
            return 0;
        }
        coada.pop_front();
        int xx = x + dx[dir];
        int yy = y + dy[dir];
        if (Valid(xx, yy, dir) && lung[xx][yy][dir] > lung[x][y][dir]){
                lung[xx][yy][dir] = lung[x][y][dir];
                coada.push_front({xx, yy, dir});
        }
        int dir2 = (dir + 1) % 8;
        if (lung[x][y][dir2] > 1 + lung[x][y][dir]){
            lung[x][y][dir2] = 1 + lung[x][y][dir];
            coada.push_back({x, y, dir2});
        }
        dir2 = (dir + 7) % 8;
        if (lung[x][y][dir2] > 1 + lung[x][y][dir]){
            lung[x][y][dir2] = 1 + lung[x][y][dir];
            coada.push_back({x, y, dir2});
        }
    }
    fout << -1;
    return 0;
}