Cod sursa(job #594601)

Utilizator rudarelLup Ionut rudarel Data 8 iunie 2011 15:17:06
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.95 kb
#include <stdio.h>
#include <limits.h>
#include <string.h>
#include <queue>
 
using namespace std;
 
#define MN (512)
 
const int move_cost[8][8] = {
    {0, 1, 2, 3, 4, 3, 2, 1},
    {1, 0, 1, 2, 3, 4, 3, 2},
    {2, 1, 0, 1, 2, 3, 4, 3},
    {3, 2, 1, 0, 1, 2, 3, 4},
    {4, 3, 2, 1, 0, 1, 2, 3},
    {3, 4, 3, 2, 1, 0, 1, 2},
    {2, 3, 4, 3, 2, 1, 0, 1},
    {1, 2, 3, 4, 3, 2, 1, 0}
},
    mover[8] = {0, -1, -1, -1, 0, 1, 1, 1},
    movec[8] = {1, 1, 0, -1, -1, -1, 0, 1};
 
struct Cfg {
    int r, c, d;
};
 
int C[MN][MN][8], m[MN][MN];
int N, M, startr, startc, endr, endc, X;
queue<Cfg> q;
 
inline int inside(int r, int c)
{
    return 0 <= r && r < N && 0 <= c && c < M;
}
 
inline Cfg make_cfg(int r, int c, int d)
{
    Cfg tmp;
    tmp.r = r; tmp.c = c; tmp.d = d;
    return tmp;
}
 
int main()
{
    freopen("car.in", "r", stdin);
    freopen("car.out", "w", stdout);
 
    int i, j, r, c, nr, nc;
 
    scanf("%d %d %d %d %d %d", &N, &M, &startr, &startc, &endr, &endc);
    --startr; --startc; --endr; --endc;
    for(r = 0; r < N; ++r) for(c = 0; c < M; ++c)
        scanf("%d", &m[r][c]);
 
    for(r = 0; r < N; ++r) for(c = 0; c < M; ++c) for(i = 0; i < 8; ++i)
        C[r][c][i] = LONG_MAX;
    for(i = 0; i < 8; ++i) if(inside(nr = startr+mover[i], nc = startc+movec[i]) && !m[nr][nc]) {
        C[nr][nc][i] = 0;
        q.push(make_cfg(nr, nc, i));
    }
 
    for(; !q.empty(); q.pop()) {
        r = q.front().r; c = q.front().c; j = q.front().d;
        for(i = 0; i < 8; ++i) if(inside(nr = r+mover[i], nc = c+movec[i]) &&
                !m[nr][nc] && C[r][c][j]+move_cost[j][i] < C[nr][nc][i]) {
            C[nr][nc][i] = C[r][c][j]+move_cost[j][i];
            q.push(make_cfg(nr, nc, i));
        }
    }
 
    for(X = LONG_MAX, i = 0; i < 8; ++i) if(C[endr][endc][i] < X)
        X = C[endr][endc][i];
    if(X == LONG_MAX)
        X = -1;
 
    printf("%d\n", X);
 
    return 0;
}