Cod sursa(job #3235766)

Utilizator Sasha_12454Eric Paturan Sasha_12454 Data 21 iunie 2024 13:06:41
Problema Car Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.29 kb
//dial
#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}, dy[] = {0, 1, 1, 1, 0, -1, -1, -1};

int n;

int m;

int xs;

int ys;

int xf;

int yf;

int cnt;

int actual;

bool a[NMAX][NMAX];

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

int dist[NMAX][NMAX];

std :: queue <std :: pair<std :: pair<int, int>, int>> q[3];

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

void dial()
{
    while(cnt)
    {
        while(q[actual].empty())
        {
            actual ++;
            actual %= 3;
        }

        int x = q[actual].front().first.first;

        int y = q[actual].front().first.second;

        int dir = q[actual].front().second;

        q[actual].pop();

        cnt --;

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

            //pastrez dir

            for(int i = -2; i <= 2; i ++)
            {
                int ac_dir = dir + i;

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

                ac_dir %= 8;

                int l = x + dx[ac_dir];

                int c = y + dy[ac_dir];

                if(inbound(l, c) && a[l][c] == 0 && dist[x][y] + abs(i) < dist[l][c])
                {
                    cnt ++;

                    q[(actual + abs(i)) % 3].push(std :: make_pair(std :: make_pair(l, c), ac_dir));

                    dist[l][c] = dist[x][y] + abs(i);
                }
            }

            /*if(inbound(x + dx[dir], y + dy[dir]) && a[x + dx[dir]][y + dy[dir]] == 0 && dist[x][y] < dist[x + dx[dir]][y + dy[dir]])
            {
                q[actual].push(std :: make_pair(std :: make_pair(x + dx[dir], y + dy[dir]), dir));

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

                cnt ++;
            }

            dir ++;

            dir %= 8;

            if(inbound(x + dx[dir], y + dy[dir]) && a[x + dx[dir]][y + dy[dir]] == 0 && dist[x][y] + 1 < dist[x + dx[dir]][y + dy[dir]])
            {
                q[(actual + 1) % 3].push(std :: make_pair(std :: make_pair(x + dx[dir], y + dy[dir]), dir));

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

                cnt ++;
            }

            dir ++;

            dir %= 8;*/
        }
    }
}

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 ++)
        {
            dist[i][j] = INF;
        }
    }

    for(int i = 0; i < 7; i ++)
    {
        q[0].push(std :: make_pair(std :: make_pair(xs, ys), i));

        cnt ++;
    }

    dist[xs][ys] = 0;

    dial();

    /*for(int i = 1; i <= n; i ++, out << '\n')
    {
        for(int j = 1; j <= m; j ++)
        {
            out << dist[i][j] << " ";
        }
    }*/

    if(dist[xf][yf] == INF)
    {
        out << -1;
    }
    else
    {
        out << dist[xf][yf];
    }

    return 0;
}