Cod sursa(job #1105637)

Utilizator tzipleatudTudor Tiplea tzipleatud Data 11 februarie 2014 22:19:47
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.65 kb
#include <fstream>
#include <cstring>
#include <queue>
#include <vector>
#define NM 510

using namespace std;

ifstream f("car.in");
ofstream g("car.out");

const int INF=0x3f3f3f3f;
const int dx[8]={1, 1, 0, -1, -1, -1, 0, 1};
const int dy[8]={0, 1, 1, 1, 0, -1, -1, -1};
int N, M, C, P;
int A[NM][NM], DP[8][NM][NM];
int sl, sc, fl, fc;
queue< pair<pair<int, int>, int> > Q[2];

int main ()
{
    f >> N >> M;
    f >> sl >> sc >> fl >> fc;
    for (int i=1; i<=N; i++)
        for (int j=1; j<=M; j++)
        {
            f >> A[i][j];
            A[i][j]=1-A[i][j];
        }

    memset(DP, INF, sizeof(DP));
    for (int d=0; d<8; d++)
    {
        Q[0].push(make_pair(make_pair(sl, sc), d));
        DP[d][sl][sc]=0;
    }

    C=0;
    P=1;
    while (!Q[C].empty() || !Q[P].empty())
    {
        if (Q[C].empty())
            swap(P, C);

        int i=Q[C].front().first.first;
        int j=Q[C].front().first.second;
        int d=Q[C].front().second;

        Q[C].pop();

        if (A[i+dx[d]][j+dy[d]]==1 && DP[d][i+dx[d]][j+dy[d]]>DP[d][i][j])
        {
            DP[d][i+dx[d]][j+dy[d]]=DP[d][i][j];
            Q[C].push(make_pair(make_pair(i+dx[d], j+dy[d]), d));
        }
        for (int nd=-1; nd<=1; nd+=2)
            if (DP[(d+nd+8)%8][i][j]>DP[d][i][j]+1)
            {
                DP[(d+nd+8)%8][i][j]=DP[d][i][j]+1;
                Q[P].push(make_pair(make_pair(i, j), (d+nd+8)%8));
            }
    }

    int ANS=INF;

    for (int d=0; d<8; d++)
        ANS=min(ANS, DP[d][fl][fc]);

    g << (ANS==INF?-1:ANS) << '\n';

    f.close();
    g.close();

    return 0;
}