You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题面翻译

题目翻译

 现有 $H$ 行 $W$ 列的矩形方格，每个方格被涂成白色或黑色。高桥君移动到白色方格需要 $1$ 秒，移动到黑色方格需要 $x$ 秒。  指定两个白色方格为起点和终点，从起点到终点有一个最大时间 $T$ ，求满足条件下 $x$ 的最大值。

各字符含义如下：

• . : 白色方格
• # : 黑色方格
• S : 起点
• G : 终点

题目保证至少经过一个黑方格，且 $x=1$ 时满足时间 $T$ . $x$ 为正整数。

题目描述

正方形のマスが縦 $H$ 行、横 $W$ 列に並んでいます。各マスは白または黒で塗られており、白マスのうち $2$ つがそれぞれスタート地点とゴール地点として指定されています。

高橋君はスタート地点から出発して $T$ 秒以内にゴール地点に到着したいです。高橋君は、各マスから上下左右に隣接する別のマスに移動することができます。このとき、移動先が白マスであれば $1$ 秒、黒マスであれば $x$ 秒の時間がかかります（移動前のマスの色は移動時間に影響しません）。ここで、 $x$ の値は高橋君がスタート地点から出発する前にあなたに選んでもらいます。 $x$ の値は正整数でなければならず、高橋君の出発後に値を変更することはできません。

高橋君が $T$ 秒以内にゴール地点に到着することが可能であるような正整数 $x$ の最大値を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$H$ $W$ $T$ $s_{1,1}$$s_{1,2}$ .. $s_{1,W}$ $s_{2,1}$$s_{2,2}$ .. $s_{2,W}$ : $s_{H,1}$$s_{H,2}$ .. $s_{H,W}$

• $1$ 行目には、 $3$ 個の整数 $H,$ $W,$ $T$ ($2$ $≦$ $H,$ $W$ $≦$ $10,$ $2$ $≦$ $T$ $≦$ $10^9$) が与えられる。これらはそれぞれ、マスの行数と列数、および高橋君の目標時間を表す。

• $2$ 行目から $H\ +\ 1$ 行目には、各マスの情報が与えられる。 $i\ +\ 1$ 行目の $j$ 文字目 $s_{i,j}$ が $i$ 行 $j$ 列目のマスに対応する。各文字の意味は以下の通り：

  • . : スタート地点にもゴール地点にも指定されていない白マス
  • S : スタート地点として指定された白マス
  • G : ゴール地点として指定された白マス
  • # : 黒マス

  これら以外の文字は $s_{i,j}$ として出現せず、 S および G はそれぞれちょうど $1$ 個ずつ出現する。また、入力では求める最大値が存在することが保証される。すなわち、少なくとも $1$ 度は黒マスに移動しなければスタート地点から出発してゴール地点に到着できないこと、および $x\ =\ 1$ のとき $T$ 秒以内にゴール地点に到着することが可能であることが保証される。

输出格式

標準出力に、 高橋君が $T$ 秒以内にゴール地点に到着することが可能であるような正整数 $x$ の最大値を出力せよ。

末尾の改行を忘れないこと。

样例 #1

样例输入 #1

2 3 10
S##
.#G

样例输出 #1

8

样例 #2

样例输入 #2

3 4 7
S##G
.##.
..#.

样例输出 #2

3

样例 #3

样例输入 #3

4 4 1000000000
S###
####
####
###G

样例输出 #3

199999999

提示

部分点

この問題には部分点が設定されている。

• $40$ 点分のテストケースは $2$ $≦$ $H,$ $W$ $≦$ $3,$ $2$ $≦$ $T$ $≦$ $30$ を満たす。
• 別の $30$ 点分のテストケースは $2$ $≦$ $T$ $≦$ $30$ を満たす。

（※ 問題 D にも部分点が設定されています。そちらもご確認ください。）

Sample Explanation 1

$i$ 行 $j$ 列目のマスを $(i,\ j)$ で表します。 $x\ =\ 8$ のとき、 $(1,\ 1)\ →\ (2,\ 1)\ →\ (2,\ 2)\ →\ (2,\ 3)$ と移動すると $1\ +\ 8\ +\ 1\ =\ 10$ 秒でゴール地点に到着することができます。 $x\ \geq\ 9$ のとき、 $10$ 秒以内にゴール地点に到着することはできません。

Sample Explanation 2

スタート地点から右に直進すると $2x\ +\ 1$ 秒でゴール地点に到達できます。遠回りすることで黒マスへの移動回数を減らすことができますが、 $x$ の値によってはかえって時間がかかってしまいます。