2016-2017 ACM-ICPC Pacific Northwest Regional Contest (Div. 1) - B: Buggy Robot ★★★☆☆

競技プログラミング Dijkstra 良問

評価

良問だが若干実装疲れた.
初め, dijkstraに見えなかった.
解くのにそんなに時間がかからなかったし若干実装重いB問題かーくらいの感覚だったけど, 解いてる人数少なくて驚いた.

問題

迷路と操作列が与えられる.
操作列はUDLR(上下左右)からなる文字列である.
スタート地点にいるロボットが操作列に従って移動する.
ただし画面外に移動したりゴール後に移動したりしない.
操作列のいくつかを削除(無視)したり任意の操作を加えたりできる.
ロボットがゴールにたどり着くために操作を削除・追加する回数の最小値を求めよ.

入力例

3 3
R..
.#.
..E
LRDD

出力例

1

考察

dp[i][y][x] := 元の操作列[0,i)に変更を加えた操作列を実行したときに地点(x,y)に居るような変更回数の最小値
とすると,

  • 今の操作列に従う (コスト0, (i,y,x) → (i+1, y', x'))
  • 次の操作を無視する (コスト1, (i,y,x) → (i+1,y,x))
  • 操作を加える (コスト1, (i,y,x) → (i+1,y,x))

の遷移がある.
(i,y,x)を頂点とするとDAGとは限らず, また, 異なるコストの辺があるのでdijkstraする.

解答

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll,ll> P;

const ll linf = 1e18;

#define FOR(i,a,b) for(ll i = (a); i < (b); ++i)
#define RFOR(i,a,b) for(ll i = (b)-1; i >= (a); --i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define EACH(i,v) for(auto&& i : v)
#define ALL(v) (v).begin(),(v).end()
#define push_back pb

template<class T>
istream& operator>>(istream& is, vector<T>& v) {
    EACH(i, v) is >> i;
    return is;
}

vector<vector<vector<ll>>> dp;

struct Node {
    ll pos, x, y, cost;
};
bool operator>(const Node& n1, const Node& n2) {
    return n1.cost > n2.cost;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll h, w; cin >> h >> w;
    auto inRange = [&](ll x, ll y) {
        return 0 <= x && x < w && 0 <= y && y < h;
    };
    vector<string> m(h); cin >> m;
    string s; cin >> s;
    const ll n = s.size();
    dp.assign(n+1, vector<vector<ll>>(h, vector<ll>(w, linf)));
    priority_queue<Node, vector<Node>, greater<Node>> Q;
    ll gx, gy;
    REP(y, h) REP(x, w) {
        if (m[y][x] == 'R') {
            Q.push({0, x, y, 0});
            dp[0][y][x] = 0;
        }
        if (m[y][x] == 'E') {
            gx = x, gy = y;
        }
    }
    auto move = [&](ll x, ll y, char op) {
        if (x == gx && y == gy) return P(x, y);
        ll dx, dy;
        if (op == 'U') dx = 0, dy = -1;
        if (op == 'R') dx = 1, dy = 0;
        if (op == 'D') dx = 0, dy = 1;
        if (op == 'L') dx = -1, dy = 0;
        ll nx = x + dx, ny = y + dy;
        if ( !inRange(nx, ny) || m[ny][nx] == '#' ) return P(x, y);
        return P(nx, ny);
    };
    const string ops = "URDL";
    while ( !Q.empty() ) {
        Node node = Q.top(); Q.pop();
        ll pos = node.pos, x = node.x, y = node.y;
        ll cost = node.cost;
        if (cost > dp[pos][y][x]) continue;
        // cout << pos << " " << x << " " << y << " " << cost << " " << dp[pos][y][x] << endl;
        if (pos < n) {
            // follow
            P p = move(x, y, s[pos]);
            ll nx, ny; tie(nx, ny) = p;
            if (dp[pos][y][x] < dp[pos+1][ny][nx]) {
                dp[pos+1][ny][nx] = dp[pos][y][x];
                Q.push({pos+1, nx, ny, dp[pos+1][ny][nx]});
            }
            // ignore
            if (dp[pos+1][y][x] > dp[pos][y][x]+1) {
                dp[pos+1][y][x] = dp[pos][y][x]+1;
                Q.push({pos+1, x, y, dp[pos+1][y][x]});
            }
        }
        // give op
        EACH(op, ops) {
            P p = move(x, y, op);
            ll nx, ny; tie(nx, ny) = p;
            if (dp[pos][y][x]+1 < dp[pos][ny][nx]) {
                dp[pos][ny][nx] = dp[pos][y][x]+1;
                Q.push({pos, nx, ny, dp[pos][ny][nx]});
            }
        }
    }
    cout << dp[n][gy][gx] << endl;
}