Cod sursa(job #457352)

Utilizator ssergiussSergiu-Ioan Ungur ssergiuss Data 18 mai 2010 23:36:44
Problema Car Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.99 kb
#include <algorithm>
#include <cassert>
#include <cctype>
#include <cmath>
#include <bitset>
#include <deque>
#include <fstream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

typedef bool int01;
typedef char cha08;
typedef short int int16;
typedef int int32;
typedef float rea32;
typedef long long int int64;
typedef double rea64;

const cha08 Input[] = "car.in";
const cha08 Output[] = "car.out";

const int32 Dim = 501;
const int32 Inf = 0x3f3f3f3f;
const int32 dx[8] = {0, -1, -1, -1, 0, 1, 1, 1};
const int32 dy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const int32 cc[8][8] = {{0, 1, 2, 3, 4, 3, 2, 1},
                        {1, 0, 1, 2, 3, 4, 3, 2},
                        {2, 1, 0, 1, 2, 3, 4, 3},
                        {3, 2, 1, 0, 1, 2, 3, 4},
                        {4, 3, 2, 1, 0, 1, 2, 3},
                        {3, 4, 3, 2, 1, 0, 1, 2},
                        {2, 3, 4, 3, 2, 1, 0, 1},
                        {1, 2, 3, 4, 3, 2, 1, 0}};

int01 f[8][Dim][Dim];
int32 N, M, XXX, X[2], Y[2];
int32 c[8][Dim][Dim], h[Dim][Dim];

struct cmp {

    int01 operator()( const pair < int32, pair <int32, int32> > &p0, const pair < int32, pair <int32, int32> > &p1 ) {

        return c[p0.first][p0.second.first][p0.second.second] > c[p1.first][p1.second.first][p1.second.second];
    }
};
priority_queue < int32, vector < pair < int32, pair <int32, int32> > >, cmp > q;

int01 Ok( int32 x, int32 y ) {

    if( x < 1 || x > N )
        return 0;
    if( y < 1 || y > M )
        return 0;

    return 1;
}

void BellFord() {

    int32 i, d, x, y;

    memset( c, Inf, sizeof( c ) );
    memset( f, false, sizeof( f ) );
    for( i = 0; i < 8; ++i ) {

        q.push( make_pair( i, make_pair( X[0], Y[0] ) ) );
        c[i][X[0]][Y[0]] = 0;
        f[i][X[0]][Y[0]] = true;
    }

    while( !q.empty() ) {

        d = q.top().first;
        x = q.top().second.first;
        y = q.top().second.second;
        q.pop();
        f[d][x][y] = false;

        for( i = 0; i < 8; ++i )
            if( Ok( x + dx[i], y + dy[i] ) && !h[x + dx[i]][y + dy[i]] && c[d][x][y] + cc[d][i] < c[i][x + dx[i]][y + dy[i]] ) {

                c[i][x + dx[i]][y + dy[i]] = c[d][x][y] + cc[d][i];
                if( f[i][x + dx[i]][y + dy[i]] == false ) {

                    q.push( make_pair( i, make_pair( x + dx[i], y + dy[i] ) ) );
                    f[i][x + dx[i]][y + dy[i]] = true;
                }
            }
    }
}

int32 main() {

    ifstream fin( Input );
    ofstream fout( Output );

    int32 i, j;

    fin >> N >> M;
    fin >> X[0] >> Y[0] >> X[1] >> Y[1];

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

    BellFord();

    for( i = 0, XXX = Inf; i < 8; ++i )
        XXX = min( XXX, c[i][X[1]][Y[1]] );

    fout << XXX;

    fin.close();
    fout.close();

    return 0;
}