D - Wizard in Maze

・問題URL

https://atcoder.jp/contests/abc176/tasks/abc176_d

・思考

・DFSかBFSで迷うけど、何回のワープでたどり着けるか、0,1,2....回の順に決まっていくイメージだからBFSがよさげ
・BFSで迷路を進み、壁に当たったら一歩前から5×5マスにワープで移動できるマス探してcost++すればいいかな？…

・キーワード

・0-1BFS
・deque

・解法

・queue使ったBFSじゃダメ。なぜなら、ワープで飛んでみたけど、実際は徒歩で行けたパターンを上書きできないから。
・上下左右進めるならcostはそのままでpush_front。進めないなら一歩戻って、周囲5×5マスに未開拓の道がないか確認してあればcost++にするのだが、ここで注意が必要。実際は徒歩で行けるマスかもしれないので、seen=falseのままで黙ってpush_backする。そうすれば、次の上下左右確認時に実際は徒歩で行けた場合にcost++しなかったことにできる。また、push_backすれば、push_frontした道を優先的に探索でき、そこでcostを決定してseen=trueにすることができる。（下のコードでは、壁はそもそもdequeに入れないので、壁のseenは若干うやむやになってる。ACだからいいの。）

・コード

int main() {
   int H, W, sx, sy, gx, gy;
   cin >> H >> W >> sx >> sy >> gx >> gy;
   sx--; sy--; gy--; gx--;
   string S[1200];
   rep(i, H)cin >> S[i];
   int cost[1200][1200];
   bool seen[1200][1200];
   rep(i, 1100) {
       rep(j, 1100)cost[i][j] = 100000000;
   }
   
   deque<pair<int, int>>d;
   d.push_front({ sx,sy });
   seen[sx][sy] = true;
   cost[sx][sy] = 0;
   
   while (!d.empty()) {
   
       pair<int, int>P = d.front();
       d.pop_front();
       int X, Y;
       tie(X, Y) = P;

       for (int i = -1; i <= 1; i++) {
           for (int j = -1; j <= 1; j++) {
               if (i + X < 0 || j + Y < 0 || i + X >= H || j + Y >= W)continue;
               if (i == 0 && j == 0)continue;
               if (abs(i) * abs(j) == 1)continue;
               if (seen[X + i][Y + j])continue;
               seen[X + i][Y + j] = true;
               
               if (S[X + i][Y + j] == '.') {
                   cost[X + i][Y + j] = cost[X][Y];
                   d.push_front({ X + i,Y + j });
               }
               
               else {
                   
                   for (int k = -2; k <= 2; k++) {
                       for (int l = -2; l <= 2; l++) {
                           if (X + k < 0 || Y + l < 0 || X + k >= H || Y + l >= W)continue;
                           if (cost[X + k][Y + l] < 100000000)continue;
                           if (S[X+ k][Y+ l] == '.') {
                               cost[X + k][Y + l] = cost[X][Y] + 1;
                               d.push_back({ X + k,Y + l });
                           }
                           
                       }
                   }
               }
           }
       }
     
   }
   
   if (cost[gx][gy] >= 100000000)cout << -1 << endl;
   else cout << cost[gx][gy] << endl;
}