Cod sursa(job #1150704)

Utilizator andreiiiiPopa Andrei andreiiii Data 23 martie 2014 14:23:19
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.23 kb
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

const int N=505, INF=0x3f3f3f3f;
const int dx[]={-1, -1, 0, 1, 1, 1, 0, -1}, dy[]={0, 1, 1, 1, 0, -1, -1, -1};

int a[N][N];

struct cell
{
    int x, y, dir;
    cell() {}
    cell(const int _x, const int _y, const int _dir) {x=_x;y=_y;dir=_dir;}
    bool ok(const int n, const int m)
    {
        if(x<1||x>n) return false;
        if(y<1||y>m) return false;
        if(a[x][y]) return false;
        return true;
    }
};

queue <cell> Q[2];
int dist[N][N][8];
cell start, finish;
int n, m;

void Solve()
{
    cell p, nxt;
    memset(dist, INF, sizeof(dist));
    for(int i=0;i<8;i++)
    {
        dist[start.x][start.y][i]=0;
        Q[0].push(cell(start.x, start.y, i));
    }
    for(int u=0;!Q[u].empty();u^=1)
    {
        for(;!Q[u].empty();Q[u].pop())
        {
            p=Q[u].front();
            if(p.x==finish.x&&p.y==finish.y)
            {
                printf("%d\n", dist[p.x][p.y][p.dir]);
                return;
            }
            ////
            nxt=cell(p.x+dx[p.dir], p.y+dy[p.dir], p.dir);
            if(nxt.ok(n, m)&&dist[nxt.x][nxt.y][nxt.dir]>dist[p.x][p.y][p.dir])
            {
                dist[nxt.x][nxt.y][nxt.dir]=dist[p.x][p.y][p.dir];
                Q[u].push(nxt);
            }
            ////
            nxt=cell(p.x, p.y, (p.dir+1)%8);
            if(dist[nxt.x][nxt.y][nxt.dir]>dist[p.x][p.y][p.dir]+1)
            {
                dist[nxt.x][nxt.y][nxt.dir]=dist[p.x][p.y][p.dir]+1;
                Q[u^1].push(nxt);
            }
            ////
            nxt=cell(p.x, p.y, (p.dir+7)%8);
            if(dist[nxt.x][nxt.y][nxt.dir]>dist[p.x][p.y][p.dir]+1)
            {
                dist[nxt.x][nxt.y][nxt.dir]=dist[p.x][p.y][p.dir]+1;
                Q[u^1].push(nxt);
            }
        }
    }
    printf("-1\n");
}

int main()
{
    freopen("car.in", "r", stdin);
    freopen("car.out", "w", stdout);
    scanf("%d%d%d%d%d%d", &n, &m, &start.x, &start.y, &finish.x, &finish.y);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            scanf("%d", &a[i][j]);
        }
    }
    Solve();
}