Cod sursa(job #2849282)

Utilizator SergiuS3003Sergiu Stancu Nicolae SergiuS3003 Data 14 februarie 2022 20:08:40
Problema Car Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.5 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define punct pair<int,int>
#define x first
#define y second
#define mp make_pair
#define nl '\n'
using namespace std;
ifstream f ( "car.in" );
ofstream g ( "car.out" );
const int NMAX = 503, INF = 1e9;
bool m[NMAX][NMAX];
int cost[NMAX][NMAX][8];
int N, M;
punct init, fin;
punct d[8] = {mp ( 1, 1 ), mp ( 1, 0 ), mp ( 1, -1 ), mp ( 0, -1 ), mp ( -1, -1 ), mp ( -1, 0 ), mp ( -1, 1 ) };
void bordare()
{
    for ( int i = 0; i <= N + 1; i++ )
        m[i][0] = m[i][M + 1] = 1;

    for ( int j = 0; j <= M + 1; j++ )
        m[0][j] = m[N + 1][j] = 1;
}
struct incotro
{
    punct p;
    int dir;
};
void initCost()
{
    for ( int i = 1; i <= N; i++ )
        for ( int j = 1; j <= M; j++ )
            for ( int dir = 0; dir < 8; dir++ )
                cost[i][j][dir] = INF;
}
void Lee ( punct init )
{
    queue<incotro>Q;

    for ( int i = 0; i < 8; i++ )
    {
        Q.push ( {init, i} );
        cost[init.x][init.y][i] = 0;
    }

    while ( !Q.empty() )
    {

        punct crt = Q.front().p;
        int dircrt = Q.front().dir;
        Q.pop();
        for ( int i = 0; i < 8; i++ )
        {
            punct vec;
            vec.x = crt.x + d[i].x;
            vec.y = crt.y + d[i].y;

            if ( m[vec.x][vec.y] == 1 )
                continue;

            int difabs = abs ( dircrt - i );
            int costcrt = cost[crt.x][crt.y][dircrt];

            if ( difabs == 0 ) ///cost 0
            {
                if ( cost[vec.x][vec.y][i] > costcrt )
                {
                    cost[vec.x][vec.y][i] = costcrt;
                    Q.push ( {vec, i} );
                }
            }
            else
                if ( difabs == 1 || difabs == 7 ) ///cost 1
                {
                    if ( costcrt + 1 < cost[vec.x][vec.y][i] )
                    {
                        cost[vec.x][vec.y][i] = costcrt + 1;
                        Q.push ( {vec, i} );
                    }
                }
                else
                    if ( difabs == 2 || difabs == 6 ) ///cost 2
                    {
                        if ( costcrt + 2 < cost[vec.x][vec.y][i] )
                        {
                            cost[vec.x][vec.y][i] = costcrt + 2;
                            Q.push ( {vec, i} );
                        }
                    }
                    else
                        if ( difabs == 3 || difabs == 5 ) ///cost 3
                        {
                            if ( costcrt + 3 < cost[vec.x][vec.y][i] )
                            {
                                cost[vec.x][vec.y][i] = costcrt + 3;
                                Q.push ( {vec, i} );
                            }
                        }
                        else
                            if ( costcrt + 4 < cost[vec.x][vec.y][i] )
                            {
                                cost[vec.x][vec.y][i] = costcrt + 4;
                                Q.push ( {vec, i} );
                            }
        }
    }
}
int main()
{
    f >> N >> M;
    f >> init.x >> init.y >> fin.x >> fin.y;

    for ( int i = 1; i <= N; i++ )
        for ( int j = 1; j <= M; j++ )
            f >> m[i][j];

    bordare();
    initCost();
    Lee ( init );
    int ans = INF;

    for ( int i = 0; i < 8; i++ )
        ans = min ( ans, cost[fin.x][fin.y][i] );

    g << ans;
    return 0;
}