Cod sursa(job #1341765)

Utilizator retrogradLucian Bicsi retrograd Data 13 februarie 2015 01:49:17
Problema Car Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.18 kb
#include<fstream>
#include<vector>
#include<queue>
#include<cstring>


using namespace std;
typedef int var;


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

const var MAXN = 501;
const var INF = (1 << 18);
const var MAXNODES = MAXN*MAXN*8+1;


struct Edge {
    var n, c;
    Edge(var a, var b) {
        n = a;
        c = b;
    }
};

vector<Edge> G[MAXNODES];
var DIST[MAXNODES];
bool INQ[MAXNODES];

var n, m;

var xi, yi, xf, yf;

bool A[MAXN][MAXN];

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

queue<var> Q;
void bellman(var start) {

    Q.push(start);
    DIST[start] = 0;
    INQ[start] = 1;
    while(!Q.empty()) {
        var node = Q.front();
        INQ[node] = 0;
        Q.pop();
        for(vector<Edge>::iterator it = G[node].begin(); it != G[node].end(); ++it) {
            Edge &e = *it;
            if(DIST[e.n] > DIST[node] + e.c) {
                DIST[e.n] = DIST[node] + e.c;
                if(!INQ[e.n]) {
                    INQ[e.n] = 1;
                    Q.push(e.n);
                }
            }
        }
    }
}


inline void coord(var nod) {
    fout<<nod%8<<" ";
    return;
    var d = nod%8;
    nod /= 8;
    nod --;
    var j = nod%n+1;
    nod++;
    var i = (nod-j)/n;

    fout<<"("<<i<<" "<<j<<" "<<d<<") ";
}

inline var node(var lin, var col, var dir) {
    DIST[(lin*(n-1)+col)*8+dir] = INF;
    return (lin*(n-1)+col)*8+dir;
}

inline void AddEdge (var node1, var node2, var cost) {
    G[node1].push_back(Edge(node2, cost));
}

inline void setup(var lin, var col) {
    for(var d=0; d<7; d++) {
        AddEdge(node(lin, col, d), node(lin, col, d+1), 1);
        AddEdge(node(lin, col, d+1), node(lin, col, d), 1);
    }
    AddEdge(node(lin, col, 0), node(lin, col, 7), 1);
    AddEdge(node(lin, col, 7), node(lin, col, 0), 1);
}

void afisListe(var lin, var col) {
    for(var d=0; d<8; d++) {
        var nod = node(lin, col, d);
        fout<<"L["<<lin<<", "<<col<<", "<<d<<"] : ";
        for(vector<Edge>::iterator it = G[nod].begin(); it != G[nod].end(); ++it) {
            coord((*it).n);
        }
        fout<<endl;
    }
}

int main() {

    fin>>n>>m;
    fin>>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 - A[i][j];
        }
    }

    //for(var i=1; i<=n; i++) {
     //   for(var j=1; j<=m; j++) {
      //      fout<<A[i][j]<<" ";
       // }
      //  fout<<endl;
   // }

    for(var i=1; i<=n; i++) {
        for(var j=1; j<=m; j++) {
            if(!A[i][j]) continue;
            setup(i, j);
            for(var d=0; d<8; d++) {
                var nx = i+DX[d];
                var ny = j+DY[d];
                if(A[nx][ny]) {
                    AddEdge(node(i, j, d), node(nx, ny, d), 0);
                }
            }
        }
    }

    var st = 0;
    var en = n*n*8+8;

    DIST[en] = INF;

    for(var d=0; d<8; d++) {
        AddEdge(st, node(xi, yi, d), 0);
        AddEdge(node(xf, yf, d), en, 0);
    }

    bellman(st);
    fout<<DIST[en];

    //afisListe(2, 4);

    return 0;
}