Cod sursa(job #141127)

Utilizator SycronVene Tian Sycron Data 22 februarie 2008 19:19:41
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.46 kb
#include<stdio.h>   
  
#define infinit 0x3f3f3f3f   
#define lg 505   
  
const int dx[] = {0, -1, -1, 0, 1, 1, 1, 0, -1};   
const int dy[] = {0, 0, 1, 1, 1, 0, -1, -1, -1};   
int n, m, px, py, fx, fy, i, j, k, rsp[lg][lg][9], end[4], cost, st, x, y, xx, yy, p, cst, s;   
char a[lg][2000], fst[lg][lg][9];   
struct ches{   
    short x, y;   
    char dir;   
};   
ches d[3][lg*lg];   
inline int fnd(int a){   
    if (a > 8)   
        return a-8;   
    if (a < 1)   
        return 8+a;   
    return a;   
}   
inline int as(int a){   
    if (a < 0)   
        return -a;   
    return a;   
}   
int main()   
{   
    freopen("car.in", "rt", stdin);   
    freopen("car.out", "wt", stdout);   
       
    scanf("%d%d", &n, &m);   
    scanf("%d%d%d%d\n", &px, &py, &fx, &fy);   
    for (i = 1; i <= n; i ++)   
        fgets(a[i], 2000, stdin);   
       
    for (i = 1; i <= 8; i ++){   
        end[0] ++;   
        d[0][end[0]].x = px, d[0][end[0]].y = py;   
        d[0][end[0]].dir = i;   
    }   
       
    st = 1;   
    cost = 0;   
    while (!s){   
        while (st <= end[0]){   
            x = d[0][st].x;   
            y = d[0][st].y;   
            i = d[0][st].dir;   
               
            for (j = -1; j < 2; j ++)   
                if (j != 0){   
                    p = fnd(i+j);   
                       
                    if (!fst[x][y][p]){   
                        end[1] ++;   
                        fst[x][y][p] = 1;   
                           
                        d[1][end[1]].x = x;   
                        d[1][end[1]].y = y;   
                        d[1][end[1]].dir = p;   
                        rsp[x][y][p] = 1+cost;   
                        //nrnod ++;   
                    }   
                    else  
                        if (1+cost < rsp[x][y][p]){   
                            end[1] ++;   
                               
                            d[1][end[1]].x = x;   
                            d[1][end[1]].y = y;   
                            d[1][end[1]].dir = p;   
                            rsp[x][y][p] = 1+cost;   
                        }   
                }   
               
            for (j = i-1; j <= i+1; j ++){   
                p = fnd(j);   
                xx = x+dx[p];   
                yy = y+dy[p];   
                cst = as(j-i);   
                   
                if (a[xx][2*(yy-1)] == '0' && xx > 0 && xx <= n && yy > 0 && yy <= m){   
                    cst = as(j-i);   
                    /*  
                    if (x == 9 && y == 13 && i == 4){  
                        fprintf(stderr, "suntem in %d si %d directia %d cu costul %d", x, y, i, cost);  
                        fprintf(stderr, "avem %d si %d  in directia %d cu %d\n", xx, yy, p, cst+cost);  
                    }  
                    */  
                    if (!fst[xx][yy][p]){   
                        end[cst] ++;   
                        fst[xx][yy][p] = 1;   
                           
                        d[cst][end[cst]].x = xx;   
                        d[cst][end[cst]].y = yy;   
                        d[cst][end[cst]].dir = p;   
                        rsp[xx][yy][p] = cst+cost;   
                        //nrnod ++;   
                    }   
                    else  
                        if (cst+cost < rsp[xx][yy][p]){   
                            end[cst] ++;   
                               
                            d[cst][end[cst]].x = xx;   
                            d[cst][end[cst]].y = yy;   
                            d[cst][end[cst]].dir = p;   
                            rsp[xx][yy][p] = cst+cost;   
                        }   
                }   
            }   
               
            st ++;   
        }   
           
        for (k = 1; k <= end[1]; k ++){   
            d[0][k].x = d[1][k].x;   
            d[0][k].y = d[1][k].y;   
            d[0][k].dir = d[1][k].dir;   
        }   
           
        cost ++;   
        end[0] = end[1], end[1] = 0;   
        st = 1;   
        if (end[0] == 0)   
            s = 1;   
    }   
       
    int min = infinit;   
    for (i = 1; i <= 8; i ++)   
        if (rsp[fx][fy][i] < min && fst[fx][fy][i])   
            min = rsp[fx][fy][i];   
    if (min != infinit)   
        printf("%d\n", min);   
    else  
        printf("-1\n");   
       
    return 0;   
}