Nu aveti permisiuni pentru a descarca fisierul grader_test17.in

Cod sursa(job #1563371)

Utilizator mariakKapros Maria mariak 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;
}