#include using namespace std; typedef long long ll; typedef vector vi; typedef vector vl; typedef complex P; typedef pair pii; #define REP(i,n) for(ll i=0;i Q; Q.push(state(sy,sx,0)); while(!Q.empty()){ state S = Q.front(); Q.pop(); int id = S.id, y = S.y, x = S.x; // DEBUG(x); // DEBUG(y); // DEBUG(id); int d = dp[id][y][x]; REP(i,(id?4:8)){ int ny = y+(id?dyb[i]:dyn[i]); int nx = x+(id?dxb[i]:dxn[i]); if(ny<0 || nx<0 || ny>=h || nx>=w)continue; if(mp[ny][nx]){ if(dp[1-id][ny][nx]!=INF)continue; dp[1-id][ny][nx] = d+1; Q.push(state(ny,nx,1-id)); }else{ if(dp[id][ny][nx]!=INF)continue; dp[id][ny][nx] = d+1; Q.push(state(ny,nx,id)); } } } // REP(x,2){ // REP(i,h){ // REP(j,w)printf("%10d",dp[x][i][j]); // printf("\n"); // } // printf("\n"); // } int ans = min(dp[0][gy][gx],dp[1][gy][gx]); if(ans==INF)ans=-1; printf("%d\n",ans); return 0; }