Cod sursa(job #2503654)

Utilizator andrei42Oandrei42O andrei42O Data 3 decembrie 2019 17:14:15
Problema Car Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.58 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("barbar.in");
ofstream g("barbar.out");
const int N = 502;
const int oo = 1000000;
int dir[8][2]={{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}},cst[8][8];
int n, m, x, y, a[N][N];
queue<tuple<int, int, int>> q;
int main()
{
    f >> n >> m;
    vector<int> linie(m+1,oo);
    vector<vector<int>> matrice(n+1,linie);
    vector<vector<vector<int>>> c(8,matrice);
    f>>x>>y;
    for(int i=0;i<8;i++)
    {
        c[i][x][y]=0;
        q.push(make_tuple(i,x,y));
    }
    f>>x>>y;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            f>>a[i][j];
    for(int i=0;i<=n+1;i++)
        a[i][0]=a[i][m+1]=1;
    for(int j=1;j<=m;j++)
        a[0][j]=a[n+1][j]=1;
    for(int i=0;i<8;i++)cst[i][0]=cst[0][i]=min(i,8-i);
    for(int i=1;i<8;i++)
        for(int j=1;j<8;j++)
            cst[i][j]=cst[i-1][j-1];
    while(q.size())
    {
        int d, i, j, co, nextco, nexti, nextj, nextd;
        tie(d,i,j)=q.front();
        q.pop();
        co=c[d][i][j];
        for(nextd=0;nextd<8;nextd++)
        {
            nextco=co+cst[d][nextd];
            nexti=i+dir[nextd][0];
            nextj=j+dir[nextd][1];
            if(!a[nexti][nextj])
                if(nextco<c[nextd][nexti][nextj])
                {
                    c[nextd][nexti][nextj]=nextco;
                    q.push(make_tuple(nextd,nexti,nextj));
                }
        }
    }
    int ans=oo;
    for(int i=0;i<8;i++)
        ans=min(ans,c[i][x][y]);
    if(ans==oo)ans=-1;
    g<<ans;
    return 0;
}