Nu aveti permisiuni pentru a descarca fisierul grader_test17.in
Cod sursa(job #1563371)
Utilizator | Data | 5 ianuarie 2016 22:52:53 | |
---|---|---|---|
Problema | Car | Scor | 80 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 1.94 kb |
#include <bits/stdc++.h>
#define maxN 502
#define inf 1000000000
#define maxD 8
using namespace std;
int n, m, sol, si, sj, fi, fj;
short int cost[maxN][maxN][maxD];
int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[] = {0, -1, -1, -1, 0, 1, 1, 1};
int Q[2][maxN * maxN];
bool a[maxN][maxN];
int mod(int x)
{
if (x >= 8)
x -= 8;
return x;
}
int ok(int x, int y)
{
if (x < 1 || y < 1 || x > n || y > m || a[x][y] == 1)
return 0;
return 1;
}
int crypt(int x, int y, int d)
{
return (((x << 9) + y) << 3) + d;
}
void decrypt(int c, int &x, int &y, int &d)
{
d = c & 7;
c >>= 3;
y = c & 511;
c >>= 9;
x = c;
}
void read()
{
int i, j;
freopen("car.in", "r", stdin);
scanf("%d %d", &n, &m);
scanf("%d %d %d %d", &si, &sj, &fi, &fj);
for (i = 1; i <= n; ++ i)
for (j = 1; j <= m; ++ j)
scanf("%d", &a[i][j]);
}
void add(int x, int y, int d, int c)
{
int i = x, j = y;
for (;ok(i, j); i += dx[d], j += dy[d])
if (!cost[i][j][d])
{
cost[i][j][d] = c;
Q[c & 1][++ Q[c & 1][0]] = (crypt(i, j, d));
if (i == fi && j == fj)
sol = c;
}
}
void solve()
{
int d, i;
sol = 0;
for (d = 0; d < 8; ++ d)
add(si, sj, d, 1);
i = 1;
while (!sol && Q[i & 1][0])
{
while (Q[i & 1][0])
{
int node = Q[i & 1][Q[i & 1][0]], x, y;
-- Q[i & 1][0];
decrypt(node, x, y, d);
add(x, y, mod(d + 1), cost[x][y][d] + 1);
add(x, y, mod(d + 7), cost[x][y][d] + 1);
}
++ i;
}
for (i = 0; i <= 8; ++ i)
if (cost[fi][fj][i] && cost[fi][fj][i] < sol)
sol = cost[fi][fj][i];
}
void write()
{
freopen("car.out", "w", stdout);
-- sol;
printf("%d\n", sol);
}
int main()
{
read();
solve();
write();
return 0;
}