TopCoder SRM707 Div 2 Med: StepsConstruct

正答率低いのはバグりやすいせいかな。発想自体はそんなに難しくない。

問題概要

原文 → TopCoder Statistics - Problem Statement

$n \times m$ の盤面があり、. は通行可能な座標、# は通行不可能な座標を表す。座標の移動は上下左右の方向のみ許されている。左上の座標からスタートし、右下の座標にちょうど $k$ ステップで到達できるルートが存在するならば、そのルートを出力せよ。なお、同じ座標に何度移動しても構わないものとする。

解説

まず普通に BFS をやってみて、右下に行くまでに最短で何ステップ必要かを求めましょう。この時点で INF になったり $k$ を超えてたりしていると明らかに無理なので弾きます。

次に、 $k$ と最短ステップの偶奇を調べましょう。これが一致していないときも弾きます。

経路復元は、ゴールから再度 BFS していくのがやりやすいと思います。ゴールからたどれば、今いる座標の隣のどこかに (スタートから今いる座標に行くまでのステップ数 - $1$ ) の座標が必ず存在するので、経路復元が可能になります。

ここまで来たら、ステップ数が $k$ になるように適当に増やせば終わりです。手っ取り早いやり方としては、右下の座標の隣のドットと右下の座標に交互に移動し続けるのが良いでしょう。

ソースコード

int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
string dir = "DURL";

int rec[100][100];
class StepsConstruct {
    public:
    string construct(vector<string> board, int k) {
        int n = board.size(), m = board[0].size();
        rep(i,0,n) rep(j,0,m) rec[i][j] = INF;
        rec[0][0] = 0;
        queue<pii> q;
        if(board[0][0] == '.') q.push(pii(0,0));

        while(!q.empty()) {
            pii t = q.front(); q.pop();
            rep(i,0,4) {
                int x = t.fr + dx[i];
                int y = t.sc + dy[i];
                if(x < 0 || x >= n || y < 0 || y >= m) continue;
                if(board[x][y] == '#') continue;
                if(rec[x][y] <= rec[t.fr][t.sc] + 1) continue;
                rec[x][y] = rec[t.fr][t.sc] + 1;
                q.push(pii(x,y));
            }
        }

        if(rec[n-1][m-1] == INF || rec[n-1][m-1] > k) return "";
        if(k % 2 != rec[n-1][m-1] % 2) return "";

        string ret = "";
        int dist = rec[n-1][m-1];
        q.push(pii(n-1, m-1));
        int repdir = -1;
        while(!q.empty()) {
            pii t = q.front(); q.pop();
            rep(i,0,4) {
                int x = t.fr + dx[i];
                int y = t.sc + dy[i];
                if(x < 0 || x >= n || y < 0 || y >= m) continue;
                if(rec[x][y] != dist - 1) continue;
                if(repdir == -1) repdir = i;
                ret += dir[i ^ 1];
                dist--;
                q.push(pii(x, y));
            }
        }
        reverse(ret.begin(), ret.end());
        while(ret.size() != k) ret = ret + dir[repdir] + dir[repdir ^ 1];
        return ret;
    }
};