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; }