当前没有测试数据。

Ex - Builder Takahashi (增强版)

得分: $600$ 分

题目描述

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

• S: 起点。方格仅有一个起点。
• G: 终点。方格仅有一个终点。
• .: 可建造的方格，可以建墙。
• O: 不可建造的方格，不能建墙。

高木打算从起点出发到达终点。当他在 $(i,j)$ 位置时，他可以向上 $(i-1,j)$，向下 $(i+1,j)$，向左 $(i,j-1)$ 或向右 $(i,j+1)$ 移动。不能离开方格或进入有墙的方格。

高橋决定在高木出发之前在一个或多个可建造方格上建墙，这样高木就无法到达终点。这里，不能选择起点和终点。

高橋是否可以建墙阻止高木到达终点？如果可以，还需要计算以下两个值:

• 最小所需墙壁数 $n$，以阻止高木到达终点
• 到达最小墙壁数的不同方法数对 $998244353$ 取模为 $r$

约束

• $2 \leq H \leq 100$
• $2 \leq W \leq 100$
• $C_{i,j}$ 是 S, G, ., 或 O。
• S 和 G 在 $C_{i,j}$ 中各出现一次。

---

输入

输入通过标准输入给出，格式如下：

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

---

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

Yes
3 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 ```

---

3 2
.G
.O
.S

No

无论高橋如何建墙，高木总能到达终点。

---

2 2
S.
.G

Yes
2 1

---

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

Yes
10 12