弾幕ゲーム [Kyoto University Programming Contest 2018 B]

https://beta.atcoder.jp/contests/kupc2018/tasks/kupc2018_b

考察過程

1. 答えは最高10桁でそれぞれ3パターンあるので、組み合わせ数は3^10
2. これは普通に全探索できる

解法

https://beta.atcoder.jp/contests/kupc2018/submissions/3313684

答えを全探索しよう。
　
まず、命令列を全て用意するにはqueueをつかってBFSのように用意しよう。
H-1回文字を後ろに付け加えることを繰り返す。
　
次に、ある文字列が目的を達成できるかを判定しよう。（run関数）
これは普通にシミュレートしていけばいい。
実装が少しめんどくさいが、まだめんどくさくない方。

int H, W;
string C[10];
//---------------------------------------------------------------------------------------------------
#define ok 1
#define ng 0
int run(string s) {
    int x, y = H-1;
    rep(xx, 0, W) if (C[H - 1][xx] == 's') x = xx;
 
    fore(c, s) {
        y--;
        if (c == 'L') {
            if (x == 0) return ng;
            x--;
        } else if (c == 'R') {
            if (x == W - 1) return ng;
            x++;
        }
        if (C[y][x] == 'x') return ng;
    }
    return ok;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W;
    rep(y, 0, H) cin >> C[y];
 
    queue<string> que;
    que.push("");
    rep(y, 0, H - 1) {
        queue<string> que2;
        while (!que.empty()) {
            string q = que.front(); que.pop();
            que2.push(q + "L");
            que2.push(q + "R");
            que2.push(q + "S");
        }
        swap(que, que2);
    }
 
    while (!que.empty()) {
        string q = que.front(); que.pop();
        if (run(q)) {
            cout << q << endl;
            return;
        }
    }
    cout << "impossible" << endl;
}