筑墙者高桥(加强版)

题目描述

有一个由 $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$;
• 达到最少墙数的方案数 $r$(对 $998244353$ 取模)。

输入格式

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

H W
C_{1,1}C_{1,2}… C_{1,W}
C_{2,1}C_{2,2}… C_{2,W}
⋮
C_{H,1}C_{H,2}… 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

数据范围

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