Cod sursa(job #3257364)

Utilizator TonyyAntonie Danoiu Tonyy Data 17 noiembrie 2024 14:23:54
Problema Car Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <bits/stdc++.h>
using namespace std;

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

const vector<int> dx({-1, -1, -1, 0, 1, 1, 1, 0});
const vector<int> dy({-1, 0, 1, 1, 1, 0, -1, -1});

int n, m, s1, s2, f1, f2, ans = INT_MAX;
const int Max = 501;
vector<vector<vector<int>>> c(8, vector<vector<int>>(Max, vector<int>(Max, INT_MAX)));
vector<vector<int>> a(Max, vector<int>(Max));
queue<tuple<int,int,int>> q[3];

bool in_mat(int x, int y)
{
    return x >= 1 && y >= 1 && x <= n && y <= m;
}

void dial(int d, int x, int y)
{
    int qn = 0, nr = 8;
    for(int i = 0; i < 8; ++i)
    {
        c[i][x][y] = 0;
        q[qn].push({i, x, y});
    }
    while(nr)
    {
        --nr;
        while(q[qn].empty())
            qn = (qn + 1) % 3;
        tie(d, x, y) = q[qn].front();
        q[qn].pop();
        for(int i = -2; i <= 2; ++i)
        {
            int nd = (d + i + 8) % 8;
            int nx = x + dx[nd];
            int ny = y + dy[nd];
            int cost = abs(i);
            if(in_mat(nx, ny) && !a[nx][ny] && c[d][x][y] + cost < c[nd][nx][ny])
            {
                ++nr;
                c[nd][nx][ny] = c[d][x][y] + cost;
                q[c[nd][nx][ny] % 3].push({nd, nx, ny});
            }
        }
    }
    for(int i = 0; i < 8; ++i)
        ans = min(ans, c[i][f1][f2]);
}

int main()
{
    fin >> n >> m >> s1 >> s2 >> f1 >> f2;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            fin >> a[i][j];

    dial(0, s1, s2);
    fout << (ans != INT_MAX ? ans : -1);

    fin.close();
    fout.close();
    return 0;
}