AT_abc243_h [ABC243Ex] Builder Takahashi (Enhanced version)

题目描述

有一个 $H \times W$ 的网格。第 $i$ 行第 $j$ 列的格子记作 $(i,j)$。
每个格子的状态用 $C_{i,j}$ 表示。每个格子的状态有以下四种之一：

• S：起点。网格上恰好有且仅有一个。
• G：终点。网格上恰好有且仅有一个。
• .：可以建墙的格子。
• O：不可以建墙的格子。

青木君从起点出发，在网格上移动，目标是到达终点。青木君在 $(i,j)$ 时，可以移动到 $(i+1,j)$、$(i,j+1)$、$(i-1,j)$、$(i,j-1)$ 中的任意一个格子。只是，不能移动到网格外，也不能移动到有墙的格子。

高桥君可以在青木君开始移动之前，选择至少一个可以建墙的格子建墙，使得无论青木君如何移动，都无法到达终点。起点和终点不能建墙。

请问高桥君能否通过建墙让青木君无法到达终点？如果可以，请计算：

• 使青木君无法到达终点所需建墙的最小格子数 $n$，以及
• 达成最小建墙数的方案数对 $998244353$ 取模的结果 $r$

请输出上述两个整数。

输入格式

输入按以下格式从标准输入给出。

$H$ $W$
$C_{1,1}$ $C_{1,2}$ $\dots$ $C_{1,W}$
$C_{2,1}$ $C_{2,2}$ $\dots$ $C_{2,W}$
$\vdots$
$C_{H,1}$ $C_{H,2}$ $\dots$ $C_{H,W}$

输出格式

如果高桥君可以通过建墙让青木君无法到达终点，输出字符串 Yes，以及题目中定义的整数 $n$、$r$，格式如下：

Yes $n$ $r$

否则输出 No。

输入输出样例 #1

输入 #1

4 3
S..
O..
..O
..G

输出 #1

Yes
3 6

输入输出样例 #2

输入 #2

3 2
.G
.O
.S

输出 #2

No

输入输出样例 #3

输入 #3

2 2
S.
.G

输出 #3

Yes
2 1

输入输出样例 #4

输入 #4

10 10
OOO...OOO.
.....OOO.O
OOO.OO.OOO
OOO..O..S.
....O.O.O.
.OO.O.OOOO
..OOOG.O.O
.O.O..OOOO
.O.O.OO...
...O..O..O

输出 #4

Yes
10 12

说明/提示

限制

• $2 \leq H \leq 100$
• $2 \leq W \leq 100$
• $C_{i,j}$ 只可能是 S、G、.、O 之一。
• S、G 在 $C_{i,j}$ 中各出现且仅出现一次。

样例解释 1

用 # 表示建墙的格子，最小建墙数的方案如下，共有 $6$ 种：

S#.   S.#   S..   S..   S..   S..
O#.   O#.   O##   O.#   O.#   O.#
#.O   #.O   #.O   ##O   .#O   .#O
..G   ..G   ..G   ..G   #.G   .#G

样例解释 2

无论高桥君如何建墙，青木君都能到达终点。

由 ChatGPT 4.1 翻译