Cod sursa(job #3324122)

Utilizator Kimberly_Brubaker_BradelyKimberly Brubaker Kimberly_Brubaker_Bradely Data 21 noiembrie 2025 10:11:31
Problema Car Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.25 kb
#include <bits/stdc++.h>
using namespace std;
int n, m;
bool mat[505][505];
int vis[505][505][10];
// 0, 45 sus, 90 sus, 135 sus, 180 sus, 45 jos, 90 jos, 135 jos
int dx[8]={0, -1, -1, -1, 0, 1, 1, 1};
int dy[8]={1, 1, 0, -1, -1, -1, 0, 1};
//int dx[8]={0, -1, -1, -1, 0, 1, 1, 1};
//int dy[8]={1, 1, 0, -1, -1, 1, 0, -1};

struct node
{
    int x, y, dir;
};
bool verif(node poz, int new_val)
{
    if(mat[poz.x][poz.y])
        return 1;
    if(vis[poz.x][poz.y][poz.dir]<=new_val)
        return 1;
    if(1>poz.x || poz.x>n || 1>poz.y || poz.y>m)
        return 1;
    return 0;
}
void bfs(node poz)
{
    queue<node>q[5];
    for(int k=0; k<8; k++)
    {
        q[0].push({poz.x, poz.y, k});
        vis[poz.x][poz.y][k]=0;
    }
    for(int i=0; i<=1000000; i++)
    {
        int cnt=0;
        while(!q[i%5].empty())
        {
            node init=q[i%5].front();
            //cout << init.x << ' ' << init.y << ' ' << init.dir << '\n';
            q[i%5].pop();
            for(int k=2; k>=-2; k--)
            {
                node new_poz={init.x+dx[(init.dir+k+8)%8], init.y+dy[(init.dir+k+8)%8], (init.dir+k+8)%8};
               // cout << new_poz.x << ' ' << new_poz.y << ' ' << new_poz.dir << ' ' << vis[new_poz.x][new_poz.y][new_poz.dir] << "*\n"; 
                if(!verif(new_poz, i+abs(k)))
                {
                    q[(i+abs(k))%5].push(new_poz);
                    vis[new_poz.x][new_poz.y][new_poz.dir]=vis[init.x][init.y][init.dir]+abs(k);
                }
            }
        }
    }
}
int main()
{
    ifstream cin ("car.in");
    ofstream cout ("car.out");
    cin >> n >> m;
    int xi, yi, xf, yf;
    cin >> xi >> yi >> xf >> yf;
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
            cin >> mat[i][j];
    }
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            for(int k=0; k<8; k++)
                vis[i][j][k]=2100000000;
        }
    }
    bfs({xi, yi, 0});
    int min1=2100000000;
    for(int k=0; k<8; k++)
    {
        if(vis[xf][yf][k]!=2100000000)
            min1=min(min1, vis[xf][yf][k]);
    }
    if(min1==2100000000)
        cout << -1;
    else
        cout << min1;
    return 0;
}