【PGBATTLE2020_せんべい3】左手法(Left-Hand Rule)​

過去問：https://products.sint.co.jp/q_list_2020
解答コード：https://products.sint.co.jp/hubfs/resource/topsic/pgb2020/code.pdf

アルゴロジックで左手探索の実装を知っていたので再現。https://www.youtube.com/watch?v=ZrsBq4TEji4

1. 進んだら左に回転。
2. 壁なら右に回転。
をするだけでよさそうです。

Q.  if (DP[y][x]>4) break？
A. ループ判定。
十字路のループ判定は、同じ場所を5回通ったらもれなくループしてるといえそう。

実装。

ll H, W;
ll sy, sx, gy, gx;
char C[1010][1010];
ll DP[1010][1010];

void leftd(ll &d){
 d=(d+3)%4;
 return ;
}
void rightd(ll &d){
 d=(d+1)%4;
 return ;
}

void debug(){
 rep(i, H){
   rep(j, W){
     cout << DP[i][j];
   }
   cout << endl;
 }
}

int main(){
 cincout();
 
 cin >> H >> W >> sy >> sx >> gy >> gx;
 --sy, --sx, --gy, --gx;
 rep(i, H) rep(j, W) cin >> C[i][j];
 ll y=sy;
 ll x=sx;
 ll d=0;
 ++DP[y][x];
 ll turn = 0;
 bool fin=false;
 while(1){
   if (y == gy && x == gx){
     fin=true;
     break;
   }
   if (DP[y][x]>4) break;
   
   leftd(d);
   bool cant=false;
   rep(n, 5){
     if (n==4){
       cant=true;
       break;
     }
     ll ny = y+dy[d];
     ll nx = x+dx[d];
     if (ny<0 || nx<0 || ny>=H || nx>=W){
       rightd(d);
       continue;
     }
     if (C[ny][nx] == '.') break;
     rightd(d);
   }
   if (cant) break;
   y += dy[d];
   x += dx[d];
   ++DP[y][x];
   ++turn;
 }
 if (!fin) turn = -1;
 cout << turn << endl;
//  debug();
}