Cod sursa(job #2206712)

Utilizator Andrei_CotorAndrei Cotor Andrei_Cotor Data 23 mai 2018 15:45:49
Problema Car Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.89 kb
#include<fstream>
#include<queue>
using namespace std;
ifstream fi("car.in");
ofstream fo("car.out");
int n,m,x,y,xx,yy,k,i,j,D[8][505][505],nd,A[505][505],c;
pair<int,pair<int,int> > val;
deque<pair<int,pair<int,int> > > Q[3];
int dx[]={-1,-1,0,1,1,1,0,-1};
int dy[]={0,1,1,1,0,-1,-1,-1};

int modul(int x)
{
    if(x<0)
        return -x;
    return x;
}

int main()
{
    fi>>n>>m;
    fi>>x>>y>>xx>>yy;
    for(i=1; i<=n; i++)
        for(j=1; j<=m; j++)
            fi>>A[i][j];
    for(k=0; k<8; k++)
        for(i=1; i<=n; i++)
            for(j=1; j<=m; j++)
                D[k][i][j]=1000000000;
    for(i=0; i<8; i++)
    {
        D[i][x][y]=0;
        Q[0].push_back({i,{x,y}});
    }
    for(i=0; i<=500000; i++)
    {
        while(!Q[i%3].empty())
        {
            val=Q[i%3].front();
            Q[i%3].pop_front();
            if(i>D[val.first][val.second.first][val.second.second])
                continue;
            if(val.second.first==xx && val.second.second==yy)
            {
                fo<<D[val.first][val.second.first][val.second.second]<<"\n";
                fi.close();
                fo.close();
                return 0;
            }
            for(j=-2; j<=2; j++)
            {
                c=modul(j);
                nd=(val.first+j+8)%8;
                if(A[val.second.first+dx[nd]][val.second.second+dy[nd]]==0 && val.second.second+dy[nd]>=1 && val.second.second+dy[nd]<=m && val.second.first+dx[nd]>=1 && val.second.first+dx[nd]<=n && D[nd][val.second.first+dx[nd]][val.second.second+dy[nd]]>i+c)
                {
                    D[nd][val.second.first+dx[nd]][val.second.second+dy[nd]]=i+c;
                    Q[(i+c)%3].push_back({nd,{val.second.first+dx[nd],val.second.second+dy[nd]}});
                }
            }
        }
    }
    fo<<"-1\n";
    fi.close();
    fo.close();
    return 0;
}