Cod sursa(job #3235863)

Utilizator Sasha_12454Eric Paturan Sasha_12454 Data 23 iunie 2024 09:18:00
Problema Car Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.76 kb
#include <bits/stdc++.h>

std :: ifstream in ("car.in");

std :: ofstream out ("car.out");

const int NMAX = 5e2 + 5;

const int INF = 2e9;

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

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

int n;

int m;

int xs;

int ys;

int xf;

int yf;

int mini = INF;

bool a[NMAX][NMAX];

bool visited[NMAX][NMAX][8];

int dist[NMAX][NMAX][8];

std :: deque <std :: pair<std :: pair<int, int>, int>> dq;

inline bool inbound(int i, int j)
{
    return i >= 1 && j >= 1 && i <= n && j <= m;
}

void bfs()
{
    while(!dq.empty())
    {
        int x = dq.front().first.first;

        int y = dq.front().first.second;

        int dir = dq.front().second;

        dq.pop_front();

        if(visited[x][y][dir] == false)
        {
            visited[x][y][dir] = true;

            if(inbound(x + dx[dir], y + dy[dir]) && visited[x + dx[dir]][y + dy[dir]][dir] == false && a[x + dx[dir]][y + dy[dir]] == false && dist[x][y][dir] < dist[x + dx[dir]][y + dy[dir]][dir])
            {
                dq.push_front(std :: make_pair(std :: make_pair(x + dx[dir], y + dy[dir]), dir));

                dist[x + dx[dir]][y + dy[dir]][dir] = dist[x][y][dir];
            }

            int ac_dir = dir + 1;

            ac_dir %= 8;

            if(visited[x][y][ac_dir] == false && dist[x][y][dir] + 1 < dist[x][y][ac_dir])
            {
                dq.push_back(std :: make_pair(std :: make_pair(x, y), ac_dir));

                dist[x][y][ac_dir] = dist[x][y][dir] + 1;
            }

            ac_dir = dir - 1;

            if(ac_dir < 0)
            {
                ac_dir += 8;
            }

            if(visited[x][y][ac_dir] == false && dist[x][y][dir] + 1 < dist[x][y][ac_dir])
            {
                dq.push_back(std :: make_pair(std :: make_pair(x, y), ac_dir));

                dist[x][y][ac_dir] = dist[x][y][dir] + 1;
            }
        }
    }
}

int main()
{

    in >> n >> m;

    in >> xs >> ys >> xf >> yf;

    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= m; j ++)
        {
            in >> a[i][j];
        }
    }

    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= m; j ++)
        {
            for(int k = 0; k < 8; k ++)
            {
                dist[i][j][k] = INF;
            }
        }
    }

    for(int i = 0; i < 8; i ++)
    {
        dq.push_front(std :: make_pair(std :: make_pair(xs, ys), i));

        dist[xs][ys][i] = 0;
    }

    bfs();

    for(int i = 0; i <8; i ++)
    {
        mini = std :: min(mini, dist[xf][yf][i]);
    }
    if(mini == INF)
    {
        out << -1;
    }
    else
    {
        out << mini;
    }

    return 0;
}