Cod sursa(job #2523676)

Utilizator Radu_FilipescuFilipescu Radu Radu_Filipescu Data 14 ianuarie 2020 16:57:23
Problema Car Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.9 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 505;
const int INF = 200000000;

int N, M;
int dp[8][NMAX][NMAX];
int mat[NMAX][NMAX];
int l1, c1, l2, c2;
int dl[8] = { -1, -1, -1, 0, 1, 1,  1,  0 };
int dc[8] = { -1,  0,  1, 1, 1, 0, -1, -1 };

deque < pair< int,int > > Q;

void Read()
{
    fin >> N >> M;
    fin >> l1 >> c1 >> l2 >> c2;

    for( int i = 1; i <= N; ++i )
      for( int j = 1; j <= M; ++j )
        fin >> mat[i][j];
}

int Cost( int dir1, int dir2 )
{
    int ans = abs( dir1 - dir2 );

    if( ans < 5 ) return ans;

    return ans - ( 8 - ans );
}

void Do()
{
    int L, C, lv, cv;

    for( int i = 0; i <= N + 1; ++i )
       mat[i][0] = mat[i][M + 1] = 1;

    for( int j = 0; j <= M + 1; ++j )
       mat[0][j] = mat[N + 1][j] = 1;

    Q.push_back( { l2, c2 } );

    while( !Q.empty() ) {
        L = Q.front().first;
        C = Q.front().second;

        Q.pop_front();

        //fout << L << ' ' << C << '\n';

        for( int i = 0; i < 8; ++i )
        {
            lv = L + dl[i];
            cv = C + dc[i];

            if( mat[lv][cv] == 0 ) {
                Q.push_back( { lv, cv });
                mat[lv][cv] = 2;
            }
            else
              if( mat[lv][cv] == 3 )
                for( int j = 0; j < 8; ++j )
                  dp[j][L][C] = dp[i][lv][cv] + Cost( j, i );
        }

        mat[L][C] = 3;

        if( L == l1 && C == c1 ) break;
    }

    /*for( int i = 0; i < 8; ++i )
      fout << i << ' ' << dp[i][2][4] << '\n';

    for( int i = 0; i < 8; ++i )
      fout << i << ' ' << dp[i][3][5] << '\n';*/

    int best_dp = INF;

    for( int i = 0; i < 8; ++i )
      best_dp = min( best_dp, dp[i][l1][c1] );

    fout << best_dp << '\n';
}

int main()
{
    Read();
    Do();

    return 0;
}