/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
N \times M のグリッドがあり、この上にプレイヤーがいます。
このグリッドの上から i 行目、左から j 列目をマス (i,j) と書きます。
このグリッドの各マスは 氷 か 岩 であり、その情報は N 個の長さ M の文字列 S_1,S_2,\dots,S_N として与えられます。
- もし S_i の j 文字目が
.なら、マス (i,j) は 氷 である。 - もし S_i の j 文字目が
#なら、マス (i,j) は 岩 である。
なお、このグリッドの外周 ( 1 行目、 N 行目、 1 列目、 M 列目の全てのマス ) は 岩 です。
最初、プレイヤーはマス (2,2) の上で停止しています。このマスは 氷 です。
プレイヤーは以下の行動を 0 度以上何度でも行うことができます。
- まず、プレイヤーは上下左右の移動方向を指定する。
- その後、プレイヤーは岩のマスにぶつかるまでその方向に移動する。厳密には以下の通りである。
- もし移動方向に隣接するマスが 氷 なら、そのマスに移動し、同じ方向に移動を継続する。
- もし移動方向に隣接するマスが 岩 なら、今いるマスに留まり、移動を終了する。
プレイヤーが触れる (通過または上で停止する) ことができる 氷 の数を求めてください。
制約
- 3 \le N,M \le 200
- S_i は
#と.からなる長さ M の文字列 - i=1 または i=N または j=1 または j=M であるとき、マス (i,j) は 岩
- マス (2,2) は 氷
入力
入力は以下の形式で標準入力から与えられる。
N M S_1 S_2 \vdots S_N
出力
答えを整数として出力せよ。
入力例 1
6 6 ###### #....# #.#..# #..#.# #....# ######
出力例 1
12
例えばマス (5,5) には以下のように移動することで上で停止することができます。
- (2,2) \rightarrow (5,2) \rightarrow (5,5)
例えばマス (2,4) には以下のように移動することで通過することができます。
- (2,2) \rightarrow (2,5) の移動中に (2,4) を通過する。
例えばマス (3,4) は通過することも上で停止することもできません。
入力例 2
21 25 ######################### #..............###...#### #..............#..#...### #........###...#...#...## #........#..#..#........# #...##...#..#..#...#....# #..#..#..###...#..#.....# #..#..#..#..#..###......# #..####..#..#...........# #..#..#..###............# #..#..#.................# #........##.............# #.......#..#............# #..........#....#.......# #........###...##....#..# #..........#..#.#...##..# #.......#..#....#..#.#..# ##.......##.....#....#..# ###.............#....#..# ####.................#..# #########################
出力例 2
215
Score : 400 points
Problem Statement
There is an N \times M grid and a player standing on it.
Let (i,j) denote the square at the i-th row from the top and j-th column from the left of this grid.
Each square of this grid is ice or rock, which is represented by N strings S_1,S_2,\dots,S_N of length M as follows:
- if the j-th character of S_i is
., square (i,j) is ice; - if the j-th character of S_i is
#, square (i,j) is rock.
The outer periphery of this grid (all squares in the 1-st row, N-th row, 1-st column, M-th column) is rock.
Initially, the player rests on the square (2,2), which is ice.
The player can make the following move zero or more times.
- First, specify the direction of movement: up, down, left, or right.
- Then, keep moving in that direction until the player bumps against a rock. Formally, keep doing the following:
- if the next square in the direction of movement is ice, go to that square and keep moving;
- if the next square in the direction of movement is rock, stay in the current square and stop moving.
Find the number of ice squares the player can touch (pass or rest on).
Constraints
- 3 \le N,M \le 200
- S_i is a string of length M consisting of
#and.. - Square (i, j) is rock if i=1, i=N, j=1, or j=M.
- Square (2,2) is ice.
Input
The input is given from Standard Input in the following format:
N M S_1 S_2 \vdots S_N
Output
Print the answer as an integer.
Sample Input 1
6 6 ###### #....# #.#..# #..#.# #....# ######
Sample Output 1
12
For instance, the player can rest on (5,5) by moving as follows:
- (2,2) \rightarrow (5,2) \rightarrow (5,5).
The player can pass (2,4) by moving as follows:
- (2,2) \rightarrow (2,5), passing (2,4) in the process.
The player cannot pass or rest on (3,4).
Sample Input 2
21 25 ######################### #..............###...#### #..............#..#...### #........###...#...#...## #........#..#..#........# #...##...#..#..#...#....# #..#..#..###...#..#.....# #..#..#..#..#..###......# #..####..#..#...........# #..#..#..###............# #..#..#.................# #........##.............# #.......#..#............# #..........#....#.......# #........###...##....#..# #..........#..#.#...##..# #.......#..#....#..#.#..# ##.......##.....#....#..# ###.............#....#..# ####.................#..# #########################
Sample Output 2
215