Cod sursa(job #981260)

Utilizator paunmatei7FMI Paun Matei paunmatei7 Data 6 august 2013 16:53:35
Problema Car Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.38 kb
#include<stdio.h>
#include<queue>
#include<fstream>
#include<string.h>

#define NMAX 507
#define INF 0x3f3f3f3f
#define MaxChar 1000000
#define verf ( (++CharB==MaxChar) ? ( in.read(Buffer,MaxChar),CharB=0 ) : (1) )

ifstream in("car.in");

using namespace std;

struct Car{
    int x, y, Dir;
};

queue < Car > q;
const int Dx[]={1, 1, 0, -1, -1, -1, 0, 1};
const int Dy[]={0, 1, 1,  1,  0, -1,-1,-1};
bool a[NMAX][NMAX];
int D[NMAX][NMAX][8];
int n, m, x1, y1, x2, y2;

Car make_Car(int x, int y, int Dir){
    Car A;
    A.x = x;
    A.y = y;
    A.Dir = Dir;
    return A;
}

long CharB = MaxChar - 1;
char Buffer[MaxChar];

void cit(int &a)
{
    bool ok = 0;
    for( ; !( (Buffer[ CharB ]>='0' && Buffer[ CharB ]<='9') || ( Buffer[ CharB ] == '-' ) ); verf )
        ;
    if ( Buffer[ CharB ] == '-' )
    {
        CharB++;
        ok=1;
    }
    for( a=0; (Buffer[ CharB ]>='0' && Buffer[ CharB ]<='9'); a*=10,a+=( Buffer[ CharB ]-'0'), verf )
        ;
    if(ok)
        a=-a;
}

int main(){
    freopen("car.in", "r", stdin);
    freopen("car.out", "w", stdout);
    cit(n), cit(m);
    cit(x1), cit(y1), cit(x2), cit(y2);
    for(int i = 1; i <= n; ++ i)
        for(int j = 1; j <= m; ++ j)
            cit(a[i][j]);
    memset(D, INF, sizeof(D));
    for(int i = 0; i < 8; ++ i)
        q.push(make_Car(x1, y1, i)), D[x1][y1][i] = 0;
    for(int i = 0; i <= m + 1; ++ i)
        a[0][i] = a[n + 1][i] = 1;
    for(int i = 0; i <= n + 1; ++ i)
        a[i][0] = a[i][m + 1] = 1;
    while(! q.empty()){
        Car nod = q.front();
        int xn = nod.x + Dx[nod.Dir];
        int yn = nod.y + Dy[nod.Dir];
        int d = nod.Dir;
        if(! a[xn][yn] && D[nod.x][nod.y][d] < D[xn][yn][d])
            D[xn][yn][d] = D[nod.x][nod.y][d], q.push(make_Car(xn, yn, d));
        d = (nod.Dir + 7) % 8;
        if(D[nod.x][nod.y][nod.Dir] + 1 < D[nod.x][nod.y][d])
            D[nod.x][nod.y][d] = D[nod.x][nod.y][nod.Dir] + 1, q.push(make_Car(nod.x, nod.y, d));
        d = (nod.Dir + 9) % 8;
        if(D[nod.x][nod.y][nod.Dir] + 1 < D[nod.x][nod.y][d])
            D[nod.x][nod.y][d] = D[nod.x][nod.y][nod.Dir] + 1, q.push(make_Car(nod.x, nod.y, d));
        q.pop();
    }
    int Min = INF;
    for(int i = 0; i < 8; ++ i)
        Min = min(Min, D[x2][y2][i]);
    if(Min == INF)
        Min = -1;
    printf("%d\n", Min);
}