駆け抜けろ！埼大山車部！！ [Maximum-Cup 2018 B]

https://beta.atcoder.jp/contests/maximum-cup-2018/tasks/maximum_cup_2018_b

解法

https://beta.atcoder.jp/contests/maximum-cup-2018/submissions/2312856

「全状態を考えてみる」という行動方針を使って解く。
全状態を考えてみると(y座標,x座標,行動1の回数,行動2の回数,現在の方向)で表現できるので、
15*15*16*16*4で2*10^5なので全状態は間に合いそう。
あとは、(H-1,W-1,A,B,?)の状態にできるかということなので、BFSによる到達可能性判定でできる。

using State = tuple<int, int, int, int, int>;
enum { UP = 0, RIGHT, DOWN, LEFT };
int dx[4] = { 0, 1, 0, -1 }, dy[4] = { -1, 0, 1, 0 };
int A, B, H, W;
string C[15];
//---------------------------------------------------------------------------------------------------
int vis[15][15][16][16][4];  // vis[y][x][a][b][dir]
#define yes "Yes"
#define no "No"
string solve() {
    stack<State> st;
    vis[1][1][0][0][2] = 1;
    st.push(State(1, 1, 0, 0, 2));
 
    while (!st.empty()) {
        int x, y, a, b, dir;
        tie(y, x, a, b, dir) = st.top();
        st.pop();
 
        if (x == W - 2 and y == H - 2 and a == A and b == B) return yes;
 
        // 行動1
        if (a < A) {
            int dir2 = (dir + 3) % 4;
            int xx = x + dx[dir2];
            int yy = y + dy[dir2];
            if (C[yy][xx] != '#' and !vis[yy][xx][a + 1][b][dir2]) {
                vis[yy][xx][a + 1][b][dir2] = 1;
                st.push(State(yy, xx, a + 1, b, dir2));
            }
        }
 
        // 行動2
        if (b < B) {
            int dir2 = (dir + 1) % 4;
            int xx = x + dx[dir2];
            int yy = y + dy[dir2];
            if (C[yy][xx] != '#' and !vis[yy][xx][a][b + 1][dir2]) {
                vis[yy][xx][a][b + 1][dir2] = 1;
                st.push(State(yy, xx, a, b + 1, dir2));
            }
        }
 
        // 行動3
        int xx = x + dx[dir];
        int yy = y + dy[dir];
        if (C[yy][xx] != '#' and !vis[yy][xx][a][b][dir]) {
            vis[yy][xx][a][b][dir] = 1;
            st.push(State(yy, xx, a, b, dir));
        }
    }
 
    return no;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> A >> B >> H >> W;
    rep(y, 0, H) cin >> C[y];
    cout << solve() << endl;
}