Cod sursa(job #2285120)

Utilizator Dobricean_IoanDobricean Ionut Dobricean_Ioan Data 18 noiembrie 2018 10:36:53
Problema Car Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <iostream>
#include<fstream>
#include<vector>
#include<bitset>
using namespace std;
const int nmax=500;
int n,m,i,li,lf,ci,cf,costul,cost,j;
int d1[]={-1,-1,-1,0,1,1,1,0};
int d2[]={-1,0,1,1,1,0,-1,-1};
bitset<nmax+5> a[8][nmax+5];
struct type
{
    int l,c,d;
}el;
vector<type> v[4*nmax*nmax+5];
bool mat[nmax+5][nmax+5],found;
void dfs(int x,int y,int dir)
{
        if(x==0||y==0||x==n+1||y==m+1||found) return;
        if(mat[x][y]==1) return;
        el.l=x;
        el.c=y;
        a[dir][x][y]=1;
        if(x==lf&&y==cf)
        {
            costul=cost;
            found=1;
            return;
        }
        if(dir>=1) el.d=dir-1;
        else el.d=7;
        if(a[el.d][x][y]==0)
        {
            v[cost+1].push_back(el);
        }
        if(dir<7) el.d=dir+1;
        else el.d=0;
        if(a[el.d][x][y]==0)
        {
            v[cost+1].push_back(el);
        }
        if(a[dir][x+d1[dir]][y+d2[dir]]==0)
            dfs(x+d1[dir],y+d2[dir],dir);
}
int main()
{
    ifstream f("car.in");
    ofstream g("car.out");
    f>>n>>m;
    f>>li>>ci>>lf>>cf;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
          f>>mat[i][j];
    //DIRECTII
    //0 ST sus
    //1 sus
    //2 DR sus
    //3 DR
    //4 DR jos
    //5 jos
    //6 ST jos
    //7 ST
    el.l=li;el.c=ci;
    for(i=0;i<8;i++)
    {
        a[i][li][ci]=1;
        el.d=i;
        v[1].push_back(el);
    }
    if(mat[li][ci]==1||mat[lf][cf]==1) found=1;
    for(cost=1;found==0;cost++)
    {
        if(cost>4*n) found=1;
        for(j=0;j<v[cost].size();j++)
        {
            dfs(v[cost][j].l,v[cost][j].c,v[cost][j].d);
        }
    }
    g<<costul-1;
    return 0;
}