https://onlinejudge.u-aizu.ac.jp/beta/room.html#RitsCamp19Day2/problems/E
前提知識
解説
https://onlinejudge.u-aizu.ac.jp/beta/review.html#RitsCamp19Day2/3419049
ダイクストラで解く。
dis[y][x] := (x,y)へ到達するための最小コスト
でダイクストラをしていくのだが、
- 上下左右にコストAで移動する
- コストBで能力を使い、周囲8方向にコストAで移動する
で移動を行う。
能力で消えた塀を状態に含める必要は無い。
もし、後々消えた塀の所を移動する事になった場合は、
それよりも前に移動すべきであり、周り道をする必要は無いからである。
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>; int H, W, A, B; string C[1010]; int vis[1010][1010]; ll dis[1010][1010]; min_priority_queue<pair<ll, int>> que; enum { UP = 0, UP_RIGHT, RIGHT, DOWN_RIGHT, DOWN, DOWN_LEFT, LEFT, UP_LEFT }; int dx[8] = { 0,1,1,1,0,-1,-1,-1 }; int dy[8] = { -1,-1,0,1,1,1,0,-1 }; //--------------------------------------------------------------------------------------------------- void _main() { cin >> H >> W >> A >> B; rep(y, 0, H) cin >> C[y]; rep(y, 0, H) rep(x, 0, W) dis[y][x] = infl; int sx, sy; rep(y, 0, H) rep(x, 0, W) if (C[y][x] == 's') { sx = x; sy = y; } dis[sy][sx] = 0; que.push({ 0, sy * 1010 + sx }); while (!que.empty()) { auto q = que.top(); que.pop(); ll c = q.first; int x = q.second % 1010; int y = q.second / 1010; if (C[y][x] == 'g') { cout << dis[y][x] << endl; return; } if (vis[y][x]) continue; vis[y][x] = 1; rep(i, 0, 8) if ((i & 1) == 0) { int xx = x + dx[i]; int yy = y + dy[i]; if (xx < 0 or W <= xx or yy < 0 or H <= yy) continue; if (C[yy][xx] == '#') continue; if (chmin(dis[yy][xx], c + A)) que.push({ dis[yy][xx], yy * 1010 + xx }); } int ok = 1; if (C[y][x] == '*') ok = 0; rep(i, 0, 8) { int xx = x + dx[i]; int yy = y + dy[i]; if (xx < 0 or W <= xx or yy < 0 or H <= yy) continue; if (C[yy][xx] == '*') ok = 0; } if (ok) { rep(i, 0, 8) { int xx = x + dx[i]; int yy = y + dy[i]; if (xx < 0 or W <= xx or yy < 0 or H <= yy) continue; int d = abs(x - xx) + abs(y - yy); if (chmin(dis[yy][xx], c + B + A * d)) que.push({ dis[yy][xx], yy * 1010 + xx }); } } } cout << "INF" << endl; }