1485 . 黑白物流公司

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

餘切
$\huge\text{owoovo is 8}$

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

100.0% (2/2)

Tags

ytp ytp2026 ytp-senior

Description

黑白物流公司採用一套精密的感應系統管理貨物進出。倉庫出口裝有一道電子鎖，與控制室內的一顆燈泡相連：唯有貨物抵達出口的瞬間燈泡恰好亮起，出口才會開啟。

倉庫地板由 $n$ 列 $m$ 行的地磚組成，地磚有兩種：黑磚（#）和白磚（.）。感應系統的運作方式如下：燈泡初始為熄滅狀態，每當有物體踏上黑磚，燈泡就切換一次狀態；踏上白磚則不觸發任何反應。

某日，一台送貨機器人接到任務，需將一批貨物從地板左上角運送至右下角。受限於倉庫走道的配置，機器人每步只能向右或向下移動至相鄰格子。

機器人的導航系統在出發前須預先規劃好路線。工程師想知道：在所有可行的路徑之中，有多少條路徑能讓機器人在抵達終點時可以順利走出倉庫？

Input Format

第一行有兩個正整數 $n, m$，代表倉庫地板的列數與行數。

接下來 $n$ 行，每行有一個長度為 $m$ 的字串，由 . 與 # 組成，依序描述倉庫地板由上至下各列的地磚。

  • $1 \leq n, m \leq 10^ 5$
  • $1 \leq n \times m \leq 5 \times 10^ 6$
  • 倉庫地板的每一格都是黑磚或白磚，且左上角的地磚必為白磚。

Output Format

輸出一個整數，代表有多少條路徑能讓機器人在抵達終點時可以順利走出倉庫。

由於答案可能非常大，請輸出對 998244353 取模後的結果。

Sample Input 1

2 2
..
.#

Sample Output 1

2

Sample Input 2

3 3
.#.
.#.
...

Sample Output 2

3

Hints

範測 1 解釋：

兩條路都只會踩到右下角的黑格，所以都是踩到一次。

範測 2 解釋：

能讓燈在終點亮著的路徑有三條：右右下下、下右右下、下右下右，其餘走法都沒辦法，所以答案是 3。

Problem Source

2026 YTP 高中組初賽 p5

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測試資料 0
2 0~21 無額外限制 15

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 1048576 65536 1 2
1 1000 1048576 65536 1 2
2 1000 1048576 65536 2
3 1000 1048576 65536 2
4 1000 1048576 65536 2
5 1000 1048576 65536 2
6 1000 1048576 65536 2
7 1000 1048576 65536 2
8 1000 1048576 65536 2
9 1000 1048576 65536 2
10 1000 1048576 65536 2
11 1000 1048576 65536 2
12 1000 1048576 65536 2
13 1000 1048576 65536 2
14 1000 1048576 65536 2
15 1000 1048576 65536 2
16 1000 1048576 65536 2
17 1000 1048576 65536 2
18 1000 1048576 65536 2
19 1000 1048576 65536 2
20 1000 1048576 65536 2
21 1000 1048576 65536 2
Submit
Back to Top