結果
問題 |
No.2708 Jewel holder
|
ユーザー |
|
提出日時 | 2024-03-31 13:41:14 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,466 bytes |
コンパイル時間 | 2,627 ms |
コンパイル使用メモリ | 172,660 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-09-30 18:14:22 |
合計ジャッジ時間 | 3,489 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 17 |
ソースコード
import std; void main () { int H, W; readln.read(H, W); auto A = new string[](H); foreach (i; 0..H) A[i] = readln.chomp; auto dp = new int[][][](H, W, H * W + 1); // dp[i][j][k] := (i, j)に宝石k個で至る場合の数 dp[0][0][1] = 1; foreach (i; 0..H) { foreach (j; 0..W) { foreach (k; 0..H * W + 1) { // 右 if (i + 1 < H) { char c = A[i + 1][j]; if (c == 'o') { if (k < H * W) dp[i + 1][j][k + 1] += dp[i][j][k]; } if (c == 'x') { if (0 < k) dp[i + 1][j][k - 1] += dp[i][j][k]; } } // 下 if (j + 1 < W) { char c = A[i][j + 1]; if (c == 'o') { if (k < H * W) dp[i][j + 1][k + 1] += dp[i][j][k]; } if (c == 'x') { if (0 < k) dp[i][j + 1][k - 1] += dp[i][j][k]; } } } } } long ans = 0; foreach (k; 0..H * W + 1) { ans += dp[H - 1][W - 1][k]; } writeln(ans); } void read (T...) (string S, ref T args) { import std.conv : to; import std.array : split; auto buf = S.split; foreach (i, ref arg; args) { arg = buf[i].to!(typeof(arg)); } }