Cod sursa(job #2638609)

Utilizator PatrickCplusplusPatrick Kristian Ondreovici PatrickCplusplus Data 29 iulie 2020 09:48:11
Problema Car Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.83 kb
#include <bits/stdc++.h>

using namespace std;

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

struct triplet{
    int x, y, dir;
};

int n, m, xx1, yy1, x2, y2, dp[505][505][8], matrix[505][505];
int dx[] = {-1, -1, 0, 1, -1, 1, 0, -1};
int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};
deque <triplet> coada;

bool Valid(int i, int j)
{
    return i >= 1 && j >= 1 && i <= n && j <= m && matrix[i][j] == 0;
}

int main(){
    fin >> n >> m >> xx1 >> yy1 >> x2 >> y2;
    for (int i = 1; i <= n; ++i){
        for (int j = 1; j <= m; ++j){
            fin >> matrix[i][j];
        }
    }
    for (int i = 0; i < 8; ++i){
        coada.push_back({xx1, yy1, i});
        dp[xx1][yy1][i] = 1;
    }
    while (!coada.empty()){
        int x = coada.front().x;
        int y = coada.front().y;
        int dir = coada.front().dir;
        coada.pop_front();
        int dir2 = dir;
        int xx = x + dx[dir2];
        int yy = y + dy[dir2];
        if (Valid(xx, yy) && dp[xx][yy][dir2] == 0){
            dp[xx][yy][dir2] = dp[x][y][dir];
            coada.push_front({xx, yy, dir2});
        }
        dir2 = (dir + 1) % 8;
        xx = x;
        yy = y;
        if (Valid(xx, yy) && dp[xx][yy][dir2] == 0){
            dp[xx][yy][dir2] = dp[x][y][dir] + 1;
            coada.push_back({xx, yy, dir2});
        }
        dir2 = (dir + 7) % 8;
        xx = x;
        yy = y;
        if (Valid(xx, yy) && dp[xx][yy][dir2] == 0){
            dp[xx][yy][dir2] = dp[x][y][dir] + 1;
            coada.push_back({xx, yy, dir2});
        }
    }
    int minim = 1e9;
    for (int i = 0; i < 8; ++i){
        if (dp[x2][y2][i] == 0) continue;
        minim = min(minim, dp[x2][y2][i]);
    }
    if (minim == 1e9){
        minim = -1;
    }
    fout << minim - 1;
    fin.close();
    fout.close();
    return 0;
}