mayoko’s diary

プロコンとかいろいろ。

Codeforces Round #325 (Div. 1) B. Phillip and Trains

Div2 A, B の絶望的な読みにくさに比べるとこちらはややマシ。まだ言いますけど Div2 A, B は関係ないこと書きすぎでホント英語弱者に優しくない💢💢

解法

dp[t][row][col] = (時間 t に row, col にいてゴールすることは可能か)をやるだけです。

const int MAXN = 111;
int n, k;
int dp[2*MAXN][3][MAXN];
vector<pii> ss(k), ts(k);

bool check(int t, int row, int col) {
    for (int i = 0; i < k; i++) {
        if (row != ss[i].first) continue;
        int c1 = ss[i].second-2*t, c2 = ts[i].second-2*t;
        if (c1 <= col && col <= c2) return false;
    }
    return true;
}

int dfs(int t, int row, int col) {
    if (col >= n) return 1;
    if (t >= 2*n) return 0;
    int& ret = dp[t][row][col];
    if (ret >= 0) return ret;
    if (!check(t-1, row, col)) return ret = 0;
    if (!check(t, row, col)) return ret = 0;
    if (!check(t, row, col+1)) return ret = 0;
    if (dfs(t+1, max(0, row-1), col+1)) return ret = 1;
    if (dfs(t+1, row, col+1)) return ret = 1;
    if (dfs(t+1, min(2, row+1), col+1)) return ret = 1;
    return ret = 0;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while (t--) {
        cin >> n >> k;
        ss.resize(k), ts.resize(k);
        vector<string> field(3);
        for (int i = 0; i < 3; i++) cin >> field[i];
        int cnt = 0;
        for (int i = 0; i < 26; i++) {
            char tar = (char)('A' + i);
            for (int j = 0; j < 3; j++) for (int l = 0; l < n; l++) {
                if (tar == field[j][l]) {
                    ss[cnt] = pii(j, l);
                    while (l < n && field[j][l] == tar) l++;
                    ts[cnt++] = pii(j, l-1);
                    break;
                }
            }
        }
        int index = -1;
        for (index = 0; index < 3; index++) if (field[index][0] == 's') break;
        memset(dp, -1, sizeof(dp));
        if (dfs(0, index, 0)) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}