Cod sursa(job #1723133)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 29 iunie 2016 19:33:49
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 kb
#include<cstdio>
#include<bitset>
#include<vector>
#define MAXN 500
using namespace std;
bitset<MAXN+5> reach[8][MAXN+5];
int n,m,li,ci,lf,cf,answer=0,ok=0;
bool a[MAXN+5][MAXN+5];
int current;
struct State{
    short int l;
    short int c;
    short int d;
};
int line[8]={-1,-1,-1,0,1,1,1,0};
int column[8]={-1,0,1,1,1,0,-1,-1};
vector<State> cost[4*MAXN*MAXN+5];
void Compute(int l,int c,int d){
    State temp;
    if(l<1||l>n||c<1||c>m||ok==1||a[l][c]==1)
        return;
    reach[d][l][c]=1;
    if(l==lf&&c==cf){
        answer=current;
        ok=1;
        return;
    }
    temp.l=l;
    temp.c=c;
    temp.d=d-1;
    if(temp.d==-1)
        temp.d=7;
    if(reach[temp.d][l][c]==0)
        cost[current+1].push_back(temp);
    temp.d=d+1;
    if(temp.d==8)
        temp.d=0;
    if(reach[temp.d][l][c]==0)
        cost[current+1].push_back(temp);
    if(reach[d][l+line[d]][c+column[d]]==0)
        Compute(l+line[d],c+column[d],d);
}
int main(){
    freopen("car.in","r",stdin);
    freopen("car.out","w",stdout);
    int i,j;
    State start;
    scanf("%d%d%d%d%d%d",&n,&m,&li,&ci,&lf,&cf);
    start.l=li;
    start.c=ci;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            scanf("%d",&a[i][j]);
    for(i=0;i<8;i++){
        reach[i][li][ci]=1;
        start.d=i;
        cost[1].push_back(start);
    }
    if(a[li][ci]==1||a[lf][cf]==1){
        printf("-1");
        return 0;
    }
    for(i=1;ok==0;i++){
        if(i>4*n){
            printf("-1");
            return 0;
        }
        current=i;
        for(j=0;j<cost[i].size();j++)
            Compute(cost[i][j].l,cost[i][j].c,cost[i][j].d);
    }
    printf("%d",answer-1);
    return 0;
}