Cod sursa(job #1275058)

Utilizator lokixdSebastian lokixd Data 24 noiembrie 2014 18:15:24
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.76 kb
#include <cstdio>
#include <cstring>
#include <queue>
 
using namespace std;
 
const int N = 505;
 
struct Position {
    int x, y, dir;
};
 
int a [N][N], c [8][N][N];
int dx [] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy [] = {-1, 0, 1, 1, 1, 0, -1, -1};
queue <Position> q [2];
int n, m;
Position S, F;
 
int main () {
    int i, j, l, l1, l2, cost;
    Position node, temp;
 
    freopen ("car.in", "r", stdin);
    freopen ("car.out", "w", stdout);
 
    scanf ("%d%d%d%d%d%d", &n, &m, &S.x, &S.y, &F.x, &F.y);
    for (i = 1; i <= n; i ++)
        for (j = 1; j <= m; j ++)
            scanf ("%d", &a [i][j]);
 
    if (S.x == F.x && S.y == F.y) {
        printf ("0\n");
        return 0;
    }
    S.dir = 0;
    q [0].push (S);
    S.dir = 1;
    q [0].push (S);
    S.dir = 2;
    q [0].push (S);
    S.dir = 3;
    q [0].push (S);
    S.dir = 4;
    q [0].push (S);
    S.dir = 5;
    q [0].push (S);
    S.dir = 6;
    q [0].push (S);
    S.dir = 7;
    q [0].push (S);
    memset (c, -1, sizeof (c));
    c [0][S.x][S.y] = 0;
    c [1][S.x][S.y] = 0;
    c [2][S.x][S.y] = 0;
    c [3][S.x][S.y] = 0;
    c [4][S.x][S.y] = 0;
    c [5][S.x][S.y] = 0;
    c [6][S.x][S.y] = 0;
    c [7][S.x][S.y] = 0;
    l = 0;
 
    while (!q [l % 2].empty ()) {
        l ++;
        l1 = (l % 2);
        l2 = ((l - 1) % 2);
        while (!q [l2].empty ()) {
            node = q [l2].front ();
            q [l2].pop ();
            temp.x = node.x + dx [node.dir];
            temp.y = node.y + dy [node.dir];
            temp.dir = node.dir;
            if (temp.x >= 1 && temp.x <= n && temp.y >= 1 && temp.y <= m && a [temp.x][temp.y] == 0) {
                if (c [temp.dir][temp.x][temp.y] == -1 || (c [temp.dir][temp.x][temp.y] != -1 && c [temp.dir][temp.x][temp.y] > c [node.dir][node.x][node.y])) {
                    q [l2].push (temp);
                    c [temp.dir][temp.x][temp.y] = c [node.dir][node.x][node.y];
                    if (temp.x == F.x && temp.y == F.y) {
                        printf ("%d\n", c [temp.dir][temp.x][temp.y]);
                        return 0;
                    }
                }
            }
 
            temp.x = node.x;
            temp.y = node.y;
            temp.dir = node.dir + 1;
            if (temp.dir == 8)
                temp.dir = 0;
            if (temp.x >= 1 && temp.x <= n && temp.y >= 1 && temp.y <= m && a [temp.x][temp.y] == 0) {
                if (c [temp.dir][temp.x][temp.y] == -1 || (c [temp.dir][temp.x][temp.y] != -1 && c [temp.dir][temp.x][temp.y] > c [node.dir][node.x][node.y] + 1)) {
                    q [l1].push (temp);
                    c [temp.dir][temp.x][temp.y] = c [node.dir][node.x][node.y] + 1;
                    if (temp.x == F.x && temp.y == F.y) {
                        printf ("%d\n", c [temp.dir][temp.x][temp.y]);
                        return 0;
                    }
                }
            }
 
            temp.x = node.x;
            temp.y = node.y;
            temp.dir = node.dir - 1;
            if (temp.dir == -1)
                temp.dir = 7;
            if (temp.x >= 1 && temp.x <= n && temp.y >= 1 && temp.y <= m && a [temp.x][temp.y] == 0) {
                if (c [temp.dir][temp.x][temp.y] == -1 || (c [temp.dir][temp.x][temp.y] != -1 && c [temp.dir][temp.x][temp.y] > c [node.dir][node.x][node.y] + 1)) {
                    q [l1].push (temp);
                    c [temp.dir][temp.x][temp.y] = c [node.dir][node.x][node.y] + 1;
                    if (temp.x == F.x && temp.y == F.y) {
                        printf ("%d\n", c [temp.dir][temp.x][temp.y]);
                        return 0;
                    }
                }
            }
        }
    }
    printf ("-1\n");
    return 0;
}