Cod sursa(job #1502506)

Utilizator andreey_047Andrei Maxim andreey_047 Data 14 octombrie 2015 18:53:01
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.95 kb
#include <bits/stdc++.h>
#define nmax 505
#define INF 9999

using namespace std;
int N,M,xi,yi,xf,yf,dp[nmax][nmax][8];
bool a[nmax][nmax];
const int dx[]={-1, -1, 0, 1, 1, 1, 0, -1};
const int dy[]={0, 1, 1, 1, 0, -1, -1, -1};

struct el{
 int x,y,dir;
   el(){};
   el(const int x1,const int y1,const int dir1){
      x = x1; y = y1; dir = dir1;
    }
 bool ok(){
  if(x < 1 || y < 1 || x > N || y > M || a[x][y]) return false;
  return true;}
};

queue<el>q[2];
inline void Solve(){
 int i;
 el cur,urm;
 memset(dp,INF,sizeof(dp));
    for(i = 0; i < 8; ++i){
       dp[xi][yi][i] = 0;
       q[0].push(el(xi,yi,i));
    }
    for(i = 0;!q[i].empty();i^=1){

        while(!q[i].empty()){
           cur = q[i].front();
           q[i].pop();
           urm = el(cur.x+dx[cur.dir],cur.y+dy[cur.dir],cur.dir);
           if(cur.x == xf && cur.y == yf){
            printf("%d\n",dp[cur.x][cur.y][cur.dir]);
            return;
           }
           if(urm.ok() && dp[urm.x][urm.y][urm.dir] > dp[cur.x][cur.y][cur.dir]){
              dp[urm.x][urm.y][urm.dir] = dp[cur.x][cur.y][cur.dir];
              q[i].push(urm);
           }
          urm = el(cur.x,cur.y,(cur.dir+1)%8);
          if(urm.ok() && dp[urm.x][urm.y][urm.dir] > dp[cur.x][cur.y][cur.dir]+1){
              dp[urm.x][urm.y][urm.dir] = dp[cur.x][cur.y][cur.dir]+1;
              q[i^1].push(urm);
           }
          urm = el(cur.x,cur.y,(cur.dir+7)%8);
          if(urm.ok() && dp[urm.x][urm.y][urm.dir] > dp[cur.x][cur.y][cur.dir]+1){
              dp[urm.x][urm.y][urm.dir] = dp[cur.x][cur.y][cur.dir]+1;
              q[i^1].push(urm);
           }
        }
    }
  printf("-1\n");
}
int main(){
    int i,j;
    freopen("car.in","r",stdin);
    freopen("car.out","w",stdout);
    scanf("%d %d\n%d%d%d%d",&N,&M,&xi,&yi,&xf,&yf);
    for(i = 1; i <= N; ++i)
        for(j = 1; j <= M; ++j)
         scanf("%d",&a[i][j]);
    Solve();
    return 0;
}