Cod sursa(job #912521)

Utilizator apopeid13Apopeid Alejandro apopeid13 Data 12 martie 2013 14:46:27
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.99 kb
#include <fstream>
#include <queue>
#include <algorithm>
using namespace std;
 
#define INF 15000000
 
int m, n, dir[505][505][8];
bool a[505][505];
 
const int dx[] = {0, -1, -1, -1, 0, 1, 1, 1},
          dy[] = {1, 1, 0, -1, -1, -1, 0, 1};
 
struct coord {
    int x, y, d;
} S, F;
queue <coord> Q[2];
 
coord init (int x, int y, int d)
{
    coord a;
    a.x = x, a.y = y, a.d = d;
    return a;
}
 
bool Check ()
{
    if (Q[0].empty() && Q[1].empty())
        return false;
    return true;
}
 
void Way ()
{
    while (Check())
    {
        int u;
        for (u = 0; Q[u].empty(); ++u);
        int i = Q[u].front().x;
        int j = Q[u].front().y;
        int d = Q[u].front().d;
        for (int K = d + 7; K <= d + 9; ++K)
        {
            int k = K % 8;
            int ii = i + dx[k];
            int jj = j + dy[k];
            int c = abs (K - (d + 8));
            if (ii >= 0 && jj >= 0 && ii < m && jj < n && !a[ii][jj] && dir[i][j][d] + c < dir[ii][jj][k])
            {
                dir[ii][jj][k] = dir[i][j][d] + c;
                if (!c)
                    Q[0].push (init (ii, jj, k));
                else
                    Q[1].push (init (ii, jj, k));
            }
        }
        Q[u].pop();         
    }
}   
 
int main ()
{
    ifstream fin ("car.in");
    fin >> m >> n >> S.x >> S.y >> F.x >> F.y;
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
        {
            fin >> a[i][j];
            for (int k = 0; k < 8; ++k)
                dir[i][j][k] = INF;
        }
    S.x--, S.y--, F.x--, F.y--;
    for (int k = 0; k < 8; ++k)
    {
        dir[S.x][S.y][k] = 0;
        Q[0].push (init (S.x, S.y, k));
    } 
    fin.close();
    ofstream fout ("car.out");
    Way ();     
    int M = INF;
    for (int i = 0; i < 8; ++i)
        M = min (M, dir[F.x][F.y][i]);
    if (M != INF)
        fout << M;
    else
        fout << "-1";
    fout.close ();
    return 0;
}