給你一個 N×M 的棋盤
這個棋盤可以用 N 個長度為 M 的字串表示
棋盤上的每一格可能是障礙物(表示為x)或是普通格子(表示為o)
令左上角為 (1,1) ,右下角為 (N,M)
保證 (1,1) 和 (N,M) 必為普通格子
在這個棋盤上只能往右或往下走 (當然,不能走到障礙物上)
然而,你最多可以可以往左或往上走一格 K 次 (也不能走到障礙物上或棋盤外)
試問有幾種相異的路徑可以從 (1,1) 出發並結束於 (N,M)
請將答案模 109+7 輸出
第一行為三個整數 N,M,K
接下來 N 行,每行有一字串 Si
Input Limits:
1≤N,M≤500
0≤K≤500
∀i,|Si|=M
∀i,j,Sij∈{x,o}
輸出一非負整數
3 3 0 ooo oxo ooo
2
2 3 1 ooo oxo
5
Unknown environment 'figure'\begin{figure}[h] \centering \includegraphics[width=0.7\textwidth]{https://iscoj.fg.tp.edu.tw/images/banner_new.png} \caption{abb\label{thename}} \end{figure}\begin{figure}[h] \centering \includegraphics[width=0.7\textwidth]{https://iscoj.fg.tp.edu.tw/images/banner_new.png} \caption{abb\label{thename}} \end{figure}
題目靈感自 2020 台北市資訊學科能力競賽