Cod sursa(job #1563338)

Utilizator akaprosAna Kapros akapros Data 5 ianuarie 2016 22:14:38
Problema Car Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.69 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, cost[maxN][maxN][maxD];
int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[] = {0, -1, -1, -1, 0, 1, 1, 1};
deque < int > Q[2];
int a[maxN][maxN];
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 + (d << 18);
}
void decrypt(int c, int &x, int &y, int &d)
{
    d = c >> 18;
    y = (c & 511);
    x = (c >> 9) & 511;
}
class InputReader
{
public:
    InputReader() {}
    InputReader(const char *file_name)
    {
        input_file = fopen(file_name, "r");
        cursor = 0;
        fread(buffer, SIZE, 1, input_file);
    }
    inline InputReader &operator >>(int &n)
    {
        while(buffer[cursor] < '0' || buffer[cursor] > '9')
        {
            advance();
        }
        n = 0;
        while('0' <= buffer[cursor] && buffer[cursor] <= '9')
        {
            n = n * 10 + buffer[cursor] - '0';
            advance();
        }
        return *this;
    }
private:
    FILE *input_file;
    static const int SIZE = 1 << 17;
    int cursor;
    char buffer[SIZE];
    inline void advance()
    {
        ++ cursor;
        if(cursor == SIZE)
        {
            cursor = 0;
            fread(buffer, SIZE, 1, input_file);
        }
    }
};
void read()
{
    int i, j;
    InputReader cin("car.in");
    cin >> n >> m;
    cin >> si >> sj >> fi >> fj;

    for (i = 1; i <= n; ++ i)
        for (j = 1; j <= m; ++ j)
            cin >> 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].push_back(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].empty())
    {
        while (!Q[i & 1].empty())
        {
            int node = Q[i & 1].front(), x, y;
            Q[i & 1].pop_front();
            decrypt(node, x, y, d);
            add(x, y, (d + 1) % maxD, cost[x][y][d] + 1);
            add(x, y, (d + 7) % maxD, 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;
}