Cod sursa(job #1289697)

Utilizator stefanzzzStefan Popa stefanzzz Data 10 decembrie 2014 10:20:12
Problema Car Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.8 kb
#include <fstream>
#include <set>
#define MAXN 505
#define DIR 8
#define INF 2000000000
#define MAXS 2000
using namespace std;
ifstream f("car.in");
ofstream g("car.out");

char s[MAXS];
int n, m, cost[MAXN][MAXN][DIR], cst, x, y, d, sol;
int dirx[DIR] = {0, -1, -1, -1, 0, 1, 1, 1}, diry[DIR] = {1, 1, 0, -1, -1, -1, 0, 1}, cost_schimb[DIR] = {0, 1, 2, 3, 4, 3, 2, 1};
pair< pair< int, int>, int > start, finish, nod;
bool a[MAXN][MAXN];

struct Comp{
    bool operator()(pair< pair<int, int>, int > x, pair< pair<int, int>, int > y){
        if(cost[x.first.first][x.first.second][x.second] == cost[y.first.first][y.first.second][y.second]){
            return x < y;
        }
        return cost[x.first.first][x.first.second][x.second] < cost[y.first.first][y.first.second][y.second];
    }
};

set< pair< pair<int, int> , int> , Comp> heap;

inline int cost_schimbare(int d1, int d2){
    d2 -= d1;
    if(d2 < 0)
        d2 += DIR;
    return cost_schimb[d2];
}

int main()
{
    int i, j, k;

    f >> n >> m;
    f >> start.first.first >> start.first.second;
    f >> finish.first.first >> finish.first.second;
    f.getline(s, MAXS, '\n');

    for(i = 1; i <= n; i++){
        f.getline(s + 1, MAXS, '\n');
        for(j = 1; j <= m; j++){
            a[i][j] = s[(j << 1) - 1] - '0';
            for(k = 0; k < DIR; k++)
                cost[i][j][k] = INF;
        }
    }

    for(i = 0; i <= n + 1; i++)
        a[i][0] = a[i][m + 1] = 1;
    for(i = 0; i <= m + 1; i++)
        a[0][i] = a[n + 1][i] = 1;

    for(i = 0; i < DIR; i++){
        start.second = i;
        cost[start.first.first][start.first.second][start.second] = 0;
        heap.insert(start);
    }

    while(!heap.empty()){
        nod = *heap.begin();
        heap.erase(nod);
        if(nod.first == finish.first)
            break;
        x = nod.first.first; y = nod.first.second; d = nod.second;
        for(i = 0; i < DIR; i++){
            if(a[x + dirx[i]][y + diry[i]] || cost_schimbare(d, i) > 2)
                continue;
            if(cost[x][y][d] + cost_schimbare(d, i) < cost[x + dirx[i]][y + diry[i]][i]){
                if(cost[x + dirx[i]][y + diry[i]][i] < INF)
                    heap.erase(make_pair(make_pair(x + dirx[i], y + diry[i]), i));
                cost[x + dirx[i]][y + diry[i]][i] = cost[x][y][d] + cost_schimbare(d, i);
                heap.insert(make_pair(make_pair(x + dirx[i], y + diry[i]), i));
            }
        }
    }

    sol = INF;
    for(i = 0; i < DIR; i++)
        if(cost[finish.first.first][finish.first.second][i] < sol)
            sol = cost[finish.first.first][finish.first.second][i];

    if(sol == INF){
        g << "-1\n";
        return 0;
    }

    g << sol << '\n';

    f.close();
    g.close();
    return 0;
}