Cod sursa(job #2536247)

Utilizator TeddyDinutaDinuta Eduard Stefan TeddyDinuta Data 1 februarie 2020 17:52:14
Problema Car Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.6 kb

#include <bits/stdc++.h>

using namespace std;
ifstream in("car.in");
ofstream out("car.out");
int n,m,a[510][510],l1,c1,l2,c2,d[510][510][3],cost,ans;
struct car
{
    int l,c;
    int d,c1;
};
int dx[]={-1,-1,0,1,1,1,0,-1};
int dy[]={0,1,1,1,0,-1,-1,-1};
deque<car> q;
car x,y;
bool isin(int l,int c)
{
    if(l<0||l>n||c<0||c>m) return 0;
    return 1;
}
void lee(int l,int c)
{
  for(int k=0;k<3;k++)
    for(int i=1;i<=n;i++)
      for(int j=1;j<=m;j++)
          d[i][j][k]=1e9;
    for(int k=0;k<3;k++)
       d[l][c][k]=0;
    q.push_back({l,c,0,0});
    while(!q.empty())
    {
        x=q.front();
        //cout<<x.l<<" "<<x.c<<" "<<x.d<<" "<<d[x.l][x.c][x.d]<<'\n';
        q.pop_front();
        for(int k=0;k<8;k++)
        {
            y.l=x.l+dx[k];
            y.c=x.c+dy[k];
            if(x.l==l&&x.c==c) cost=0;
            else cost=min(abs(k-x.d),8-max(k,x.d)+min(x.d,k));
            if(cost<=2&&isin(y.l,y.c)&&a[y.l][y.c]==0)
            {
                if(d[x.l][x.c][x.c1]+cost<d[y.l][y.c][cost])
                {
                    d[y.l][y.c][cost]=d[x.l][x.c][x.c1]+cost;
                    if(cost==0) q.push_front({y.l,y.c,k,cost});
                    else q.push_back({y.l,y.c,k,cost});
                }
            }
        }
    }
}
int main()
{
    in>>n>>m;
    in>>l1>>c1>>l2>>c2;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
          in>>a[i][j];
    lee(l1,c1);
    ans=1e9;
    for(int i=0;i<3;i++) {
        ans=min(ans,d[l2][c2][i]);
    }
    if(ans!=1e9) out<<ans;
    else out<<-1;
    return 0;
}