はまやんはまやんはまやん

hamayanhamayan's blog

New Year and Buggy Bot [Good Bye 2017 B]

http://codeforces.com/contest/908/problem/B

縦H(=N),横W(=M)の盤面がある。
"."が空白, "#"が壁,"S"がスタート,"E"がゴールである。
次に命令列Sが与えられ、命令は0123のいずれかである。
ここで命令0123に上下左右を割り当てて、命令列の通り動かした時にゴールに到達できる組み合わせ数を数えよ。
なお、途中で壁にぶつかったり、枠外に出た場合はゴール失敗とする。

解法

http://codeforces.com/contest/908/submission/33769521

全探索+シミュレーション
命令に上下左右を割り当てる組合せを全探索する。
これはnext_permutationでやると良い。
あとは、その割り当てを使ってそのままシミュレーションをする。
四方への移動はdx,dy変数を使ったテクを使うとやりやすい。

int H, W;
string B[101];
string S;
int dx[4] = { 0, 1, 0, -1 }, dy[4] = { -1, 0, 1, 0 };
int sx, sy;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W;
    rep(y, 0, H) cin >> B[y];
    cin >> S;

    rep(y, 0, H) rep(x, 0, W) if (B[y][x] == 'S') sx = x, sy = y;

    vector<int> v;
    rep(i, 0, 4) v.push_back(i);
    int ans = 0;
    do {
        int x = sx, y = sy;
        int ok = 0;
        fore(c, S) {
            int cc = c - '0';
            x = x + dx[v[cc]];
            y = y + dy[v[cc]];
            if (x < 0 or W <= x or y < 0 or H <= y) break;
            if (B[y][x] == '#') break;
            if (B[y][x] == 'E') {
                ok = 1;
                break;
            }
        }
        if (ok) ans++;
    } while (next_permutation(v.begin(), v.end()));
    cout << ans << endl;
}