ABC341 C - Takahashi Gets Lost

■考えたこと

全探索をすると計算量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;
}