結果

問題 No.2430 Damage Zone
コンテスト
ユーザー ID 21712
提出日時 2025-05-04 14:16:40
言語 Go
(1.23.4)
結果
AC  
実行時間 39 ms / 2,000 ms
コード長 1,675 bytes
コンパイル時間 11,904 ms
コンパイル使用メモリ 240,252 KB
実行使用メモリ 22,780 KB
最終ジャッジ日時 2025-05-04 14:16:54
合計ジャッジ時間 13,347 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

import . "fmt"

func main() {
	var h,w,k int
	Scan(&h,&w,&k)
	s := make([]string, h)
	for i := range s {
		Scan(&s[i])
	}
	dp := make([][][]int, h+w+2)
	for i := range dp {
		dp[i] = make([][]int, h)
		for j := range dp[i] {
			dp[i][j] = make([]int, w)
		}
	}
	visited := make([][]bool, h)
	for i := range visited {
		visited[i] = make([]bool, w)
	}
	const Mod = 998244353
	dp[0][0][0] = 1
	cur := []int{0,0}
	for i := 0; i < h+w+1; i++ {
		tmp := []int{}
		for len(cur) > 0 {
			l := len(cur)
			y, x := cur[l-2], cur[l-1]
			cur = cur[:l-2]
			if x + 1 < w {
				switch s[y][x+1] {
					case '.':
						for j := 0; j <= i; j++ {
							dp[j][y][x+1] += dp[j][y][x]
							dp[j][y][x+1] %= Mod
						}
						if !visited[y][x+1] {
							visited[y][x+1] = true
							tmp = append(tmp, y, x+1)
						}
					case 'o':
						for j := 0; j <= i && j+1 < k; j++ {
							dp[j+1][y][x+1] += dp[j][y][x]
							dp[j+1][y][x+1] %= Mod
						}
						if !visited[y][x+1] {
							visited[y][x+1] = true
							tmp = append(tmp, y, x+1)
						}
				}
			}
			if y + 1 < h {
				switch s[y+1][x] {
					case '.':
						for j := 0; j <= i; j++ {
							dp[j][y+1][x] += dp[j][y][x]
							dp[j][y+1][x] %= Mod
						}
						if !visited[y+1][x] {
							visited[y+1][x] = true
							tmp = append(tmp, y+1, x)
						}
					case 'o':
						for j := 0; j <= i && j+1 < k; j++ {
							dp[j+1][y+1][x] += dp[j][y][x]
							dp[j+1][y+1][x] %= Mod
						}
						if !visited[y+1][x] {
							visited[y+1][x] = true
							tmp = append(tmp, y+1, x)
						}
				}
			}
		}
		cur = tmp
	}
	ans := 0
	for i := 0; i < k; i++ {
		ans += dp[i][h-1][w-1]
		ans %= Mod
	}
	Println(ans)
}
0