Cod sursa(job #1112625)

Utilizator smaraldaSmaranda Dinu smaralda Data 19 februarie 2014 21:41:53
Problema Car Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.35 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 n, m, di[] = {-1, -1, 0, 1, 1, 1, 0, -1}, dj[] = {0, 1, 1, 1, 0, -1, -1, -1};
bool grid[NMAX + 5][NMAX + 5], vis[NMAX + 5][NMAX + 5][8];
vector <POINT> cost[NMAX + 5];
vector <POINT>::iterator it;

void print() {
    int i, j;
    for(i = 1; i <= n; i++, fprintf(stderr, "\n"))
        for(j = 1; j <= m; j++)
            fprintf(stderr, "%d ", grid[i][j]);
    fprintf(stderr, "\n\n");
}

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

    while(grid[newx][newy] == 0 && !vis[newx][newy][dir]) {
        cost[c].push_back(POINT(newx, newy, dir));

        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, c, 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 = 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++) {
        vis[si][sj][k] = 1;

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

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

    c = 0;
    while(c <= NMAX) {
        for(it = cost[c].begin(); it != cost[c].end(); it++) {
            if(vis[it->x][it->y][it->dir] == 1)
                continue;
            else
                vis[it->x][it->y][it->dir] = 1;

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

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

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

        cost[c].clear();
        ++c;
    }

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