■考えたこと
全探索をすると計算量O(HWN) = O(125 x 10^6)であり間に合うか心配だったが
この方針で実装してACした。
ACしたコードは下記。
int main() { int h, w, n; cin >> h >> w >> n; string t; cin >> t; vector<string> s(h); for (int i = 0; i < h; i++) cin >> s[i]; int ans = 0; for (int hi = 0; hi < h; hi++) { for (int wj = 0; wj < w; wj++) { if (s[hi][wj] != '.') continue; int i = hi, j = wj; bool ok = true; for (int v = 0; v < n; v++) { if (t[v] == 'L') j -= 1; if (t[v] == 'R') j += 1; if (t[v] == 'U') i -= 1; if (t[v] == 'D') i += 1; if (i < 0 || i > h || j < 0 || j > w) ok = false; if (s[i][j] != '.') ok = false; if (!ok) break; } if (ok) ans++; } } cout << ans << endl; }