Cod sursa(job #1289716)

Utilizator stefanzzzStefan Popa stefanzzz Data 10 decembrie 2014 10:54:26
Problema Car Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.83 kb
#include <fstream>
#include <set>
#include <queue>
#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, act, newx, newy;
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;
queue< pair<pair<int, int>, int > > q[3];
bool a[MAXN][MAXN], uz[MAXN][MAXN][DIR], gata;

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

inline int mod3(int x){
    return (x > 2)?(x-3):x;
}

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;
        q[0].push(start);
    }

    while(1){
        if(q[act].empty()){
            act = mod3(act + 1);
            if(q[act].empty())
                break;
        }

        while(!q[act].empty()){
            nod = q[act].front();
            q[act].pop();
            if(nod.first == finish.first){
                gata = 1;
                break;
            }
            x = nod.first.first; y = nod.first.second; d = nod.second;
            if(uz[x][y][d])
                continue;
            uz[x][y][d] = 1;
            for(i = 0; i < DIR; i++){
                cst = cost_schimbare(d, i);
                newx = x + dirx[i];
                newy = y + diry[i];
                if(a[newx][newy] || cst > 2)
                    continue;
                if(cost[x][y][d] + cst < cost[newx][newy][i]){
                    cost[newx][newy][i] = cost[x][y][d] + cst;
                    q[mod3(act + cst)].push(make_pair(make_pair(newx, newy), i));
                }
            }
        }

        if(gata)
            break;

        act = mod3(act + 1);
    }

    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;
}