Cod sursa(job #1342172)

Utilizator retrogradLucian Bicsi retrograd Data 13 februarie 2015 16:35:32
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.91 kb
#include<fstream>
#include<vector>
#include<queue>

using namespace std;
typedef int var;

ifstream fin("car.in");
ofstream fout("car.out");

#define MAXN 502


struct Node {
    var x, y, d;
    Node(var a, var b, var z) {
        x = a;
        y = b;
        d = z;
        //c = t;
    }
    Node() {}
};

var DX[] = {-1, 0, 1, 1, 1, 0, -1, -1},
    DY[] = {-1, -1, -1, 0, 1, 1, 1, 0};


var e1, e2;
Node Q1[MAXN*MAXN*2], Q2[MAXN*MAXN*2];

bool COMP[MAXN][MAXN][8];
var n, m, xi, yi, xf, yf;
bool A[MAXN][MAXN];

bool anal(Node node) {

    if(COMP[node.x][node.y][node.d]) {
        return 0;
    }

    if(node.x == xf && node.y == yf) {
        return 1;
    }

    COMP[node.x][node.y][node.d] = 1;

    Q2[++e2] = node;

    var nx = node.x + DX[node.d];
    var ny = node.y + DY[node.d];

    if(A[nx][ny] != 0 && !COMP[nx][ny][node.d])
        return anal(Node(nx, ny, node.d));

    return 0;
}

void raise() {

    e1 = 0;

    for(var i=1; i<=e2; i++) {
        Node node = Q2[i];

        var nd = (node.d + 1)%8;
        var ld = (node.d + 7)%8;

        if(!COMP[node.x][node.y][nd]) {
            Q1[++e1] = Node(node.x, node.y, nd);
        }
        if(!COMP[node.x][node.y][ld]) {
            Q1[++e1] = Node(node.x, node.y, ld);
        }
    }
}


int main() {


    fin>>n>>m>>xi>>yi>>xf>>yf;
    for(var i=1; i<=n; i++) {
        for(var j=1; j<=m; j++) {
            fin>>A[i][j];
            A[i][j] ^= 1;
        }
    }

    e2 = 0;
    for(var d=0; d<8; d++) {
        if(anal(Node(xi, yi, d))) {
            fout<<0;
            return 0;
        }
    }

    for(var depth = 1; e2; depth++) {
        raise();
        e2 = 0;
        for(var i=1; i<=e1; i++) {
            if(anal(Q1[i])) {
                fout<<depth;
                return 0;
            }
        }
    }

    fout<<-1;

    return 0;
}