Cod sursa(job #2415664)

Utilizator osiaccrCristian Osiac osiaccr Data 26 aprilie 2019 13:40:34
Problema Car Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.38 kb
#include <bits/stdc++.h>
#define DEF 510

using namespace std;

struct pozitie {
    int x;
    int y;
    int dir;
};

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

int n, m, M[DEF][DEF], dp[DEF][DEF][8], Fr[DEF][DEF][8];

const int INF = numeric_limits<int>::max();

int dx[] = { -1, -1, +0, +1, +1, +1, +0, -1 };
int dy[] = { +0, +1, +1, +1, +0, -1, -1, -1 };

pair < int, int > start, finish;

queue < pozitie > Q;

int main () {

    fin >> n >> m >> start.first >> start.second >> finish.first >> finish.second;

    for (int i = 1; i <= n; ++ i) {
        for (int j = 1; j <= m; ++ j) {
            fin >> M[i][j];

            for (int d = 0; d < 8; ++ d) {
                dp[i][j][d] = INF;
            }
        }
    }

    for (int i = 0; i <= 7; ++ i) {
        dp[start.first][start.second][i] = 0;
        Fr[start.first][start.second][i] = 1;
        Q.push ({start.first, start.second, i});
    }

    while (!Q.empty ()) {

        int x = Q.front().x;
        int y = Q.front().y;
        int dir = Q.front().dir;
        Q.pop ();

        int new_x = x + dx[dir];
        int new_y = y + dy[dir];
        if (new_x >= 1 and new_x <= n and new_y >= 1 and new_y <= m and M[new_x][new_y] == 0 and dp[new_x][new_y][dir] > dp[x][y][dir]) {
            dp[new_x][new_y][dir] = dp[x][y][dir];
            if (Fr[new_x][new_y][dir] == false) {
                Fr[new_x][new_y][dir] = true;
                Q.push ({new_x, new_y, dir});
            }
        }

        int new_dir = (dir + 1) % 8;
        if (dp[x][y][new_dir] > dp[x][y][dir] + 1) {
            dp[x][y][new_dir] = dp[x][y][dir] + 1;
            if (Fr[x][y][new_dir] == false) {
                Fr[x][y][new_dir] = true;
                Q.push ({x, y, new_dir});
            }
        }

        new_dir = dir - 1;
        if (new_dir < 0)
            new_dir = 7;
        if (dp[x][y][new_dir] > dp[x][y][dir] + 1) {
            dp[x][y][new_dir] = dp[x][y][dir] + 1;
            if (Fr[x][y][new_dir] == false) {
                Fr[x][y][new_dir] = true;
                Q.push ({x, y, new_dir});
            }
        }
    }

    int minim = INF;
    for (int i = 0; i < 8; ++ i) {
        minim = min (minim, dp[finish.first][finish.second][i]);
    }

    if (minim == INF)
        fout << "-1";
    else
        fout << minim;

    return 0;
}