Cod sursa(job #217959)

Utilizator catalina5catalina serban catalina5 Data 30 octombrie 2008 23:47:04
Problema Car Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.18 kb
#include<iostream>
#include<fstream>

using namespace std;

ifstream fin("car.in");
ofstream fout("car.out");

const int dx1[] = {0, -1, -1, 0, 1, 1, 1, 0, -1};
const int dy1[] = {0, 0, 1, 1, 1, 0, -1, -1, -1};

int a[503][503],xi,yi,xf,yf,n,m,dx[3][5000][9],dy[3][5000][9],dir[503],sl[503],nrnum,sf[4],cost,q,s1[503][503];

void bordare(){
    for (int i=0; i<=m+1;i++){
        a[0][i]=1;
        a[n+1][i]=1;
    }
    for (int i=0; i<=n+1;i++){
        a[i][0]=1;
        a[i][m+1]=1;
    }
}

void citire(){
    fin>>n>>m>>xi>>yi>>xf>>yf;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            fin>>a[i][j];
}

int num(int x, int y){
    s1[x][y]=50000;
    int nr=0;
    nr++;
    for(int i=1;i<=8;i++){
        int x1= x+dx1[i],y1=y+dy1[i];
        if (s1[x1][y1]==0&&a[x1][y1]==0)
            num(x1, y1);
    }
    return nr;
}
int ciclu(int x){
    if(x<1)
        return x+8;
    if(x>8)
        return x-8;
    return x;
}

void drum(){
    int viz[503][503],nn,nn1[503][503];
    sf[0]=1;
    for(int i=1;i<=8;i++){
        dx[0][1][i]=xi;
        dy[0][1][i]=yi;
    }
    nrnum=num(xi,yi);
    for(int k=0;k<nrnum;){
        q++;
        while (q<=sf[0]){
            for(int i=1;i<=8;i++){
                int x=dx[0][q][i];
                int y=dy[0][q][i];
            for(int j=i-2;j<=i+2;j ++){
                    int j1=ciclu(j);
                    int x1=x+dx1[j1];
                    int y1=y+dy1[j1];
                    if(a[x1][y1]==0){
                        if(i<j)
                            nn=j-i;
                        else
                            nn=i-j;
                        if (nn1[x1][y1]==0){
                            sf[nn]++;
                            nn1[x1][y1]=1;
                            dx[nn][sf[nn]][j1]=x1;
                             dy[nn][sf[nn]][j1]=y1;
                            s1[x1][y1] =cost+nn;
                        }
                        else
                            if (nn+cost <s1[x1][y1]){
                                sf[nn]++;
                                dx[nn][sf[nn]][j1]=x1;
                             dy[nn][sf[nn]][j1]=y1;
                            s1[x1][y1] =cost+nn;

                            }
                    }
                }
            if(viz[x][y]==0){
                viz[x][y]++;
                k++;
            }
            }

        }
         int i=1;

            for (k=1;k<=sf[i];k++)
                for (int j=1;j<=8;j++){
                    dx[i-1][k][j]=dx[i][k][j];
                    dy[i-1][k][j]=dy[i][k][j];
                }
            i++;
            for (k=1;k<=sf[i];k++)
                for (int j=1;j<=8;j++){
                    dx[i-1][k][j]=dx[i][k][j];
                    dy[i-1][k][j]=dy[i][k][j];
                }
        q=1;
        cost ++;
        sf[0]=sf[1];
        sf[1]=sf[2];
        sf[2] = 0;
    }
}

int main(){
    citire();
    bordare();
    drum();
    if(s1[xf][yf]==50000)
        fout<<-1<<"\n";
    else
        fout<<s1[xf][yf]<<"\n";
    fin.close();
    fout.close();
    return 0;
}