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`。

### 限制 - $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 翻译