Cod sursa(job #141127)
Utilizator | 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;
}