Cod sursa(job #2536900)

Utilizator TeddyDinutaDinuta Eduard Stefan TeddyDinuta Data 2 februarie 2020 19:39:17
Problema Car Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.02 kb
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
class InParser {
private:
    FILE *fin;
    char *buff;
    int sp;

    char read_ch() {
        ++sp;
        if (sp == 4096) {
            sp = 0;
            fread(buff, 1, 4096, fin);
        }
        return buff[sp];
    }

public:
    InParser(const char* nume) {
        fin = fopen(nume, "r");
        buff = new char[4096]();
        sp = 4095;
    }

    InParser& operator >> (int &n) {
        char c;
        while (!isdigit(c = read_ch()) && c != '-');
        int sgn = 1;
        if (c == '-') {
            n = 0;
            sgn = -1;
        } else {
            n = c - '0';
        }
        while (isdigit(c = read_ch())) {
            n = 10 * n + c - '0';
        }
        n *= sgn;
        return *this;
    }

    InParser& operator >> (long long &n) {
        char c;
        n = 0;
        while (!isdigit(c = read_ch()) && c != '-');
        long long sgn = 1;
        if (c == '-') {
            n = 0;
            sgn = -1;
        } else {
            n = c - '0';
        }
        while (isdigit(c = read_ch())) {
            n = 10 * n + c - '0';
        }
        n *= sgn;
        return *this;
    }
};
int n,m,a[510][510],l1,c1,l2,c2,d[510][510][8],cost,ans,nd,mod[20];
bool ok[510][510][8];
struct car
{
    int l,c;
    int d;
};
int dx[]={-1,-1,0,1,1,1,0,-1};
int dy[]={0,1,1,1,0,-1,-1,-1};
queue<car> q[1500];
car x,y;
void dial(int l,int c)
{
  for(int k=0;k<8;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<8;k++)
    {
       d[l][c][k]=0;
       if(l+dx[k]>0&&l+dx[k]<=n&&c+dy[k]>0&&c+dy[k]<=m&&a[l+dx[k]][c+dy[k]]==0) {
          q[0].push({l+dx[k],c+dy[k],k});
          d[l+dx[k]][c+dy[k]][k]=0;
       }
    }
    int idx=0;
    while(1)
    {
        int temp=idx;
        while(q[idx].size()==0&&idx<n+m)
            idx++;
        if(idx==n+m) break;
        x=q[idx].front();
        q[idx].pop();
        if(ok[x.l][x.c][x.d]==1) continue;
        ok[x.l][x.c][x.d]=1;
        for(int k=-2;k<=2;k++)
        {
            cost=abs(k);
            nd=(x.d+k+8)%8;
            y.l=x.l+dx[nd];
            y.c=x.c+dy[nd];
            if(y.l>0&&y.l<=n&&y.c>0&&y.c<=m&&a[y.l][y.c]==0)
            {
                if(y.l==l2&&y.c==c2)
                {
                    ans=d[x.l][x.c][x.d]+cost;
                    return;
                }
                if(d[x.l][x.c][x.d]+cost<d[y.l][y.c][nd])
                {
                    d[y.l][y.c][nd]=d[x.l][x.c][x.d]+cost;
                    q[d[y.l][y.c][nd]].push({y.l,y.c,nd});
                }
            }
        }
    }
}
int main()
{
    InParser fin("car.in");
    ofstream fout("car.out");
    fin>>n>>m;
    fin>>l1>>c1>>l2>>c2;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
          fin>>a[i][j];
    ans=1e9;
    dial(l1,c1);
    if(ans!=1e9) fout<<ans;
    else fout<<-1;
    return 0;
}