Cod sursa(job #1112658)

Utilizator smaraldaSmaranda Dinu smaralda Data 19 februarie 2014 22:16:44
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.4 kb
#include<stdio.h>
#include<queue>
#include<vector>
using namespace std;

const int NMAX = 500;

struct POINT {
    int x, y, dir;
    POINT (int x = 0, int y = 0, int dir = 0) {
        this->x = x;
        this->y = y;
        this->dir = dir;
    }
};

int c, n, m, di[] = {-1, -1, 0, 1, 1, 1, 0, -1}, dj[] = {0, 1, 1, 1, 0, -1, -1, -1}, dmin[NMAX + 5][NMAX + 5][8];
bool grid[NMAX + 5][NMAX + 5];
vector <POINT> cost[3];
vector <POINT>::iterator it;

void fill (int x, int y, int dir, int cst) {
    int newx = x + di[dir], newy = y + dj[dir];

    while(grid[newx][newy] == 0 && cst + c < dmin[newx][newy][dir]) {
        cost[cst].push_back(POINT(newx, newy, dir));
        dmin[newx][newy][dir] = cst + c;

        newx += di[dir];
        newy += dj[dir];
    }
}

int main() {
    freopen("car.in","r",stdin);
    freopen("car.out","w",stdout);
    int k, si, sj, fi, i, j, fj, newi, newj;
    POINT pos;

    scanf("%d%d%d%d%d%d",&n,&m,&si,&sj,&fi,&fj);
    for(i = 1; i <= n; i++)
        for(j = 1; j <= m; j++)
            scanf("%d",&grid[i][j]);

    for(i = 1; i <= n; i++)
        for(j = 1; j <= m; j++)
            for(k = 0; k < 8; k++)
                dmin[i][j][k] = 2e9;

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

    for(k = 0; k < 8; k++) {
        dmin[si][sj][k] = 0;

        newi = si + di[k];
        newj = sj + dj[k];
        while(grid[newi][newj] == 0) {
            cost[0].push_back(POINT(newi, newj, k));
            dmin[newi][newj][k] = 0;

            newi += di[k];
            newj += dj[k];
        }
    }

    c = 0;
    while(! (cost[0].empty() && cost[1].empty() && cost[2].empty()) ) {
        for(it = cost[0].begin(); it != cost[0].end(); it++) {
            if(dmin[it->x][it->y][it->dir] < c)
                continue;

            if(it->x == fi && it->y == fj) {
                printf("%d\n",c);
                return 0;
            }

            fill(it->x, it->y, (it->dir + 7) % 8, 1);
            fill(it->x, it->y, (it->dir + 1) % 8, 1);

            fill(it->x, it->y, (it->dir + 2) % 8, 2);
            fill(it->x, it->y, (it->dir + 6) % 8, 2);
        }

        cost[0] = cost[1];
        cost[1] = cost[2];
        cost[2].clear();

        ++c;
    }

    printf("-1\n");
    return 0;
}