← 返回题目列表

AtCoder · abc243_h

Ex. 建造者高桥(增强版)

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

有一个网格 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,以实现最少的墙壁数量。

约束

  • 2 \leq H \leq 100
  • 2 \leq W \leq 100
  • C_{i,j} is S, G, .,或 O.
  • 每个 S 和 G 恰好出现一次 C_{i,j}.

输入

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

H W
C_{1,1}C_{1,2}\dotsC_{1,W}
C_{2,1}C_{2,2}\dotsC_{2,W}
\vdots
C_{H,1}C_{H,2}\dotsC_{H,W}

输出

如果可以建造墙壁来阻止 Aoki 到达目标,则打印字符串 Yes 和整数 n 和 r 在问题陈述中定义,格式如下:

Yes
n r

否则,打印 No.


示例输入 1

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

示例输出 1

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

示例输入 2

3 2
.G
.O
.S

示例输出 2

No

无论高桥如何筑墙,青木总能达到目标。


示例输入 3

2 2
S.
.G

示例输出 3

Yes
2 1

示例输入 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