Cod sursa(job #2537718)

Utilizator DariusDCDarius Capolna DariusDC Data 3 februarie 2020 21:45:54
Problema Car Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.1 kb
#include <bits/stdc++.h>

using namespace std;

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

const int nmax = 505;
int n, m;
int sx, sy, fx, fy;
struct el
{
    int x, y, c, dir;
};

int mat[nmax][nmax];
int dist[nmax][nmax][10];
queue <el> c1, c2;

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

inline void read()
{
    fin >> n >> m;
    fin >> sx >> sy >> fx >> fy;
    int i, j;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m;j++)
    {
        fin >> mat[i][j];
        for (int k = 0; k <= 8; k++)
            dist[i][j][k] = 2e9;
    }
}

inline bool ok(el b)
{
    return (b.x >= 1 && b.x <= n && b.y <= m && b.x >= 1 && mat[b.x][b.y] == 0);
}

inline void bfs()
{
    el a, b;
    for (int i = 0; i < 8; i++)
        c1.push({sx, sy, 0, i});
    while (!c1.empty())
    {
        while (!c1.empty())
        {
            a = c1.front();
            c1.pop();
            b.x = a.x + dx[a.dir];
            b.y = a.y + dy[a.dir];
            b.c = a.c;
            b.dir = a.dir;
            if (ok(b) && dist[b.x][b.y][b.dir] > b.c)
            {
                dist[b.x][b.y][b.dir] = b.c;
                c1.push(b);
            }
            b.x = a.x;
            b.y = a.y;
            b.c = a.c + 1;
            b.dir = b.dir + 1;
            if (b.dir > 7)
                b.dir = 0;
            if (ok(b) && dist[b.x][b.y][b.dir] > b.c)
            {
                dist[b.x][b.y][b.dir] = b.c;
                c2.push(b);
            }
            b.dir = a.dir - 1;
            if (b.dir < 0)
                b.dir = 7;
            if (ok(b) && dist[b.x][b.y][b.dir] > b.c)
            {
                dist[b.x][b.y][b.dir] = b.c;
                c2.push(b);
            }
        }
        while (!c2.empty())
        {
            c1.push(c2.front());
            c2.pop();
        }
    }
    int ans = 2e9;
    for (int i = 0; i < 8; i++)
        ans = min(ans, dist[fx][fy][i]);
    fout << (ans != 2e9 ? ans : -1);
}

int main()
{
    read();
    bfs();
    return 0;
}