Cod sursa(job #2638678)

Utilizator PatrickCplusplusPatrick Kristian Ondreovici PatrickCplusplus Data 29 iulie 2020 12:56:23
Problema Car Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.96 kb
#include <fstream>
#include <queue>
#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;
};
queue <triplet> q1, q2;
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] = 0;
        q1.push({xi, yi, k});
    }
    int cost = 0;
    while (q1.size() > 0){
        while (q1.size() > 0){
            int x = q1.front().x, y = q1.front().y, dir = q1.front().dir;
            if (x == xf && y == yf){
                fout << cost;
                return 0;
            }
            q1.pop();
            if (Valid(x + dx[dir], y + dy[dir], dir) && lung[x + dx[dir]][y + dy[dir]][dir] == 1e9){
                q1.push({x + dx[dir], y + dy[dir], dir});
                lung[x + dx[dir]][y + dy[dir]][dir] = cost;
            }
            int dir2 = (dir + 1) % 8;
            if (Valid(x, y, dir2) && lung[x][y][dir2] == 1e9){
                q2.push({x, y, dir2});
            }
            dir2 = (dir + 7) % 8;
            if (Valid(x, y, dir2) && lung[x][y][dir2] == 1e9){
                q2.push({x, y, dir2});
            }
        }
        ++cost;
        while (q2.size() > 0){
            int x = q2.front().x, y = q2.front().y, dir = q2.front().dir;
            q2.pop();
            if (lung[x][y][dir] == 1e9){
                lung[x][y][dir] = cost;
                q1.push({x, y, dir});
            }
        }
    }
    fout << -1;
    return 0;
}