102437: [AtCoder]ABC243 Ex - Builder Takahashi (Enhanced version)

Memory Limit：256 MB Time Limit：2 S
Judge Style：Text Compare Creator：
Submit：0 Solved：0

Description

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, ., or O.
  • Each of S and G appears 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}$$\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}$

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

Input

Output

分数：600分 部分 问题描述 有一个包含$H \times W$个方格的网格。让$(i,j)$表示从顶部数第$i$行、从左数第$j$列的方格。 $C_{i,j}$表示每个方格的状态。每个方格处于以下四种状态之一。
  • S: 起点。网格中只有一个起点。
  • G: 终点。网格中只有一个终点。
  • .: 可建造方格，可以在此建造墙壁。
  • O: 不可建造方格，不能在此建造墙壁。
Aoki打算从起点开始到达终点。当他处于$(i,j)$时，他可以前往$(i+1,j)$、$(i,j+1)$、$(i-1,j)$或$(i,j-1)$。不允许离开网格或进入有墙壁的方格。 Takahashi决定在Aoki开始之前，在他选择的一个或多个可建造方格上建造墙壁，使得Aoki无法到达终点。这里，起点和终点不能被选择。 Takahashi是否有可能建造墙壁来阻止Aoki到达终点？如果可能，还计算以下两个值：
  • 阻止Aoki到达终点所需的最小墙壁数量$n$，和
  • 以$998244353$为模，实现该最小墙壁数量的方案数$r$。
部分 约束条件
  • $2 \leq H \leq 100$
  • $2 \leq W \leq 100$
  • $C_{i,j}$是S、G、.或O。
  • S和G在$C_{i,j}$中分别出现一次。
部分 输入 输入格式如下： ```lua $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}$ ``` 部分 输出 如果有可能建造墙壁来阻止Aoki到达终点，按照以下格式输出字符串Yes和定义在问题描述中的整数$n$和$r$： ```python Yes $n$ $r$ ``` 否则，输出No。 部分 样例输入 1 ```less 4 3 S.. O.. ..O ..G ``` 部分 样例输出 1 ```python Yes 3 6 ``` 让#表示要建造墙壁的方格。实现最小墙壁数量的六种方式如下： ```less 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 ```less 3 2 .G .O .S ``` 部分 样例输出 2 ```python No ``` 无论Takahashi如何建造墙壁，Aoki总是可以到达终点。 部分 样例输入 3 ```less 2 2 S. .G ``` 部分 样例输出 3 ```python Yes 2 1 ``` 部分 样例输入 4 ```less 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 ```python Yes 10 12 ```

Source/Category

加入题单

上一题 下一题 算法标签：