/ 
Time Limit: 4 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
縦横 H \times W マスのグリッドがあります。上から i 行目、左から j 列目のマスを (i,j) と表します。
各マスの状態は C_{i,j} で表されます。各マスの状態は次の 4 つのいずれかです。
S: スタート地点。グリッド上にちょうど 1 つだけ存在する。G: ゴール地点。グリッド上にちょうど 1 つだけ存在する。.: 壁を建ててよいマス。O: 壁を建ててはいけないマス。
青木君はスタート地点を出発してグリッド上を移動してゴール地点へ行こうとしています。青木君は (i,j) にいるときにマス (i+1,j),(i,j+1),(i-1,j),(i,j-1) のいずれかに移動することができます。ただし、グリッドの外に出るような移動や、壁があるマスへの移動を行うことはできません。
高橋君は、青木君が移動を開始する前に壁を建ててよいマスを 1 マス以上選んで壁を建てることで、青木君がどのように移動してもゴール地点へ行くことができないようにすることにしました。ただし、スタート地点およびゴール地点は選ぶことができません。
高橋君は青木君がゴールできないように壁を建てることができますか？さらに、壁を建てられる場合は
- 青木君がゴールできないように壁を建てるときの最小枚数 n 、および
- 最小枚数を達成する壁の立て方が何通りあるかを 998244353 で割ったあまり r
の 2 つも合わせて計算してください。
制約
- 2 \leq H \leq 100
- 2 \leq W \leq 100
- C_{i,j} は
S,G,.,Oのいずれかである。 S,Gは C_{i,j} の中でちょうど 1 回だけ登場する。
入力
入力は以下の形式で標準入力から与えられる。
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}
出力
青木君がゴールできないように壁を建てられる場合は、文字列 Yes 、および問題文中で定義された整数 n, r を以下の形式で出力せよ。
Yes n r
そうでない場合は No を出力せよ。
入力例 1
4 3 S.. O.. ..O ..G
出力例 1
Yes 3 6
壁を建てるマスを # で表すと、最小枚数を達成する壁の建て方は次の 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
Score : 600 points
Problem Statement
There is a grid with H \times W squares. Let (i,j) denote the square at the i-th row from the top and j-th column from the left.
C_{i,j} represents the state of each square. Each square is in one of the following four states.
S: The starting point. The grid has exactly one starting point.G: The goal. The grid has exactly one goal..: A constructible square, where a wall can be built.O: An unconstructible square, where a wall cannot be built.
Aoki intends to start at the starting point and get to the goal. When he is at (i,j), he can go to (i+1,j), (i,j+1), (i-1,j), or (i,j-1). It is not allowed to exit the grid or enter a square with a wall.
Takahashi decides to build a wall on one or more constructible squares of his choice before Aoki starts so that there is no way for Aoki to reach the goal. Here, the starting point and the goal cannot be chosen.
Is it possible for Takahashi to build walls to prevent Aoki from reaching the goal? If it is possible, also compute the two values below:
- the minimum number n of walls needed to prevent Aoki from reaching the goal, and
- the number of ways modulo 998244353, r, to achieve that minimum number of walls.
Constraints
- 2 \leq H \leq 100
- 2 \leq W \leq 100
- C_{i,j} is
S,G,., orO. - Each of
SandGappears exactly once in C_{i,j}.
Input
Input is given from Standard Input in the following format:
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}
Output
If it is possible to build walls to prevent Aoki from reaching the goal, print the string Yes and the integers n and r defined in the Problem Statement, in the following format:
Yes n r
Otherwise, print No.
Sample Input 1
4 3 S.. O.. ..O ..G
Sample Output 1
Yes 3 6
Let # represent a square to build a wall on. The six ways to achieve the minimum number of walls are as follows:
S#. S.# S.. S.. S.. S.. O#. O#. O## O.# O.# O.# #.O #.O #.O ##O .#O .#O ..G ..G ..G ..G #.G .#G
Sample Input 2
3 2 .G .O .S
Sample Output 2
No
Regardless of how Takahashi builds walls, Aoki can always reach the goal.
Sample Input 3
2 2 S. .G
Sample Output 3
Yes 2 1
Sample Input 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
Sample Output 4
Yes 10 12