Cod sursa(job #3239267)

Utilizator GabrielPopescu21Silitra Gabriel - Ilie GabrielPopescu21 Data 3 august 2024 21:58:07
Problema Car Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.76 kb
#include <bits/stdc++.h>
using namespace std;

const int dx[]= {-1, -1, -1, 0, 1, 1, 1, 0};
const int dy[]= {-1, 0, 1, 1, 1, 0, -1, -1};
int dist[505][505][8], n, m, xs, ys, xf, yf;
bitset<505> a[505];
deque<tuple<int,int,int>> dq;

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

void bfs()
{
    for (int i = 0; i < 8; ++i)
    {
        dist[xs][ys][i] = 0;
        dq.push_back({xs, ys, i});
    }

    while (!dq.empty())
    {
        int i, j, dir;
        tie(i, j, dir) = dq.front();
        dq.pop_front();

        int x = i + dx[dir];
        int y = j + dy[dir];
        if (inside(x, y) && !a[x][y] && dist[x][y][dir] > dist[i][j][dir]) // verificam pt. 0 grade (cost 0)
        {
            dist[x][y][dir] = dist[i][j][dir];
            dq.push_front({x, y, dir});
        }

        for (int k = -1; k <= 1; k += 2) // ne rotim cu 45 de grade
        {
            int new_dir = (dir + k + 8) % 8;
            if (dist[i][j][new_dir] > dist[i][j][dir] + 1)
            {
                dist[i][j][new_dir] = dist[i][j][dir] + 1;
                dq.push_back({i, j, new_dir});
            }
        }
    }
}

int main()
{
    ifstream cin("car.in");
    ofstream cout("car.out");
    cin >> n >> m >> xs >> ys >> xf >> yf;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
        {
            int x;
            cin >> x;
            a[i][j] = x;
        }

    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] = INT_MAX;

    bfs();

    int ans = INT_MAX;
    for (int i = 0; i < 8; ++i)
        ans = min(ans, dist[xf][yf][i]);

    cout << ans;

    return 0;
}