ABC213E - Stronger Takahashi

問題

https://atcoder.jp/contests/abc213/tasks/abc213_e

略説

パンチを行うのは必要になったタイミングでよい

あるマスから上下左右の移動可能なマスに重み0の辺、パンチを行うことで進めるようになるマスに重み1の辺を貼り、最短経路を求める(01BFS)

計算量はO(HW)となる

ACコード

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long
using namespace std;

constexpr int INF = 1<<30;
constexpr int dy[] = {-1,0,1,0};
constexpr int dx[] = {0,1,0,-1};

int H, W;
string S[550];
int dis[550][550];

void solve() {
    cin >> H >> W;
    for (int i=0; i<H; i++) cin >> S[i];
    deque<pair<int,int>> deq;
    deq.push_back(make_pair(0,0));
    for (int i=0; i<H; i++) fill(dis[i], dis[i]+W, INF);
    dis[0][0] = 0;
    while (!deq.empty()) {
        auto [y, x] = deq.front();
        deq.pop_front();
        for (int i=0; i<4; i++) {
            int y2 = y+dy[i], x2 = x+dx[i];
            if (y2<0 || H<=y2 || x2<0 || W<=x2) continue;
            if (S[y2][x2] == '#') continue;
            if (dis[y2][x2] <= dis[y][x]) continue;
            dis[y2][x2] = dis[y][x];
            deq.push_front(make_pair(y2, x2));
        }
        for (int i=-2; i<=2; i++) for (int j=-2; j<=2; j++) {
            if (i==0 && j==0) continue;
            if (abs(i)==2 && abs(j)==2) continue;
            int y2 = y+i, x2 = x+j;
            if (y2<0 || H<=y2 || x2<0 || W<=x2) continue;
            if (dis[y2][x2] <= dis[y][x]+1) continue;
            dis[y2][x2] = dis[y][x]+1;
            deq.push_back(make_pair(y2, x2));
        }
    }
    cout << dis[H-1][W-1] << '\n';
}

signed main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    solve();
    return 0;
}