Cod sursa(job #217936)

Utilizator zombie_testertest test zombie_tester Data 30 octombrie 2008 22:05:48
Problema Car Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
# include <cstdio>
# include <vector>

using namespace std;

# define FIN "car.in"
# define FOUT "car.out"
# define min(a,b) (a<b?a:b)
# define inf 1000000
# define MAXN 510

int N,M,xi,yi,xf,yf,i,j,len;
int ux,uy;
int A[MAXN][MAXN];
int E[MAXN][MAXN];
vector <int> Cx;
vector <int> Cy;
int dx[8] = {0,0,1,1,1,-1,-1,-1};
int dy[8] = {-1,1,-1,0,1,-1,0,1};
int co[8] = {0,0,1,2,1,1,2,1};

     int main()
     {
         freopen(FIN,"r",stdin);
         freopen(FOUT,"w",stdout);
         
         scanf("%d%d",&N,&M);
         scanf("%d%d%d%d",&xi,&yi,&xf,&yf);
         
         for (i = 1; i <= N; ++i)
           for (j = 1; j <= M; ++j)
             {
                scanf("%d",&A[i][j]);
                E[i][j] = inf;
             }
         
         E[xi][yi] = 0;
         Cx.push_back(xi);
         Cy.push_back(yi);
         len = 0;
         
         for (i = 0; i <= len; ++i)
           for (j = 0; j < 8; ++j)
             if (!A[Cx[i]+dx[j]][Cy[i]+dy[j]] && Cx[i]+dx[j]<=N && Cy[i]+dy[j]<=M)
               if (E[Cx[i]+dx[j]][Cy[i]+dy[j]]>E[Cx[i]][Cy[i]]+co[j])
                 {
                    len++;
                    Cx.push_back(Cx[i]+dx[j]);
                    Cy.push_back(Cy[i]+dy[j]);
                    E[Cx[i]+dx[j]][Cy[i]+dy[j]]=E[Cx[i]][Cy[i]]+co[j];
                 }
              
         if (E[xf][yf] != inf) printf("%d",E[xf][yf]);
           else printf("-1");
    
         return 0;
     }