B - Visibility Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200

問題文

H 行、横 W 列のマス目があり、いくつかのマスには障害物が置かれています。
上から i 番目、左から j 番目のマスをマス (i, j) と表すことにします。
H 個の文字列 S_1, S_2, S_3, \dots, S_H が与えられます。S_ij 文字目はマス (i, j) の状態を表し、# なら障害物が置かれていることを、. なら障害物が置かれていないことを表します。
このマス目上のあるマスからあるマスが見えるとは、2 つのマスが同じ行または列にあり、2 つのマスの間 (2 つのマス自身を含む) に障害物が 1 つも置かれていないことを意味します。
このマス目上のマスであって、マス目 (X, Y) から見えるもの (マス (X, Y) 自身を含む) の数を求めてください。

制約

  • 1 \le H \le 100
  • 1 \le W \le 100
  • 1 \le X \le H
  • 1 \le Y \le W
  • S_i. および # のみからなる長さ W の文字列
  • マス (X, Y) に障害物は置かれていない

入力

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

H W X Y
S_1
S_2
S_3
\hspace{3pt} \vdots
S_H

出力

答えを出力せよ。


入力例 1

4 4 2 2
##..
...#
#.#.
.#.#

出力例 1

4

以下がマス (2, 2) から見えるマスです。

  • マス (2, 1)
  • マス (2, 2)
  • マス (2, 3)
  • マス (3, 2)

入力例 2

3 5 1 4
#....
#####
....#

出力例 2

4

行または列が同じでも、間に障害物があるようなマスは見えません。


入力例 3

5 5 4 2
.#..#
#.###
##...
#..#.
#.###

出力例 3

3

Score : 200 points

Problem Statement

We have a grid of H horizontal rows and W vertical columns, where some of the squares contain obstacles.
Let (i, j) denote the square at the i-th row from the top and j-th column from the left.
You are given H strings S_1, S_2, S_3, \dots, S_H. The j-th character of S_i describes the square (i, j); # means the square contains an obstacle, and . means it does not.
We say a square is visible from another when it is on the same row or the same column, and there is no obstacle between them (including themselves).
Print the number of squares visible from the square (X, Y) (including (X, Y) itself).

Constraints

  • 1 \le H \le 100
  • 1 \le W \le 100
  • 1 \le X \le H
  • 1 \le Y \le W
  • S_i is a string of length W consisting of . and #.
  • The square (X, Y) does not contain an obstacle.

Input

Input is given from Standard Input in the following format:

H W X Y
S_1
S_2
S_3
\hspace{3pt} \vdots
S_H

Output

Print the answer.


Sample Input 1

4 4 2 2
##..
...#
#.#.
.#.#

Sample Output 1

4

The squares visible from the square (2, 2) are:

  • (2, 1)
  • (2, 2)
  • (2, 3)
  • (3, 2)

Sample Input 2

3 5 1 4
#....
#####
....#

Sample Output 2

4

Even if two squares are on the same row or the same column, they are not visible from each other when there are obstacles between them.


Sample Input 3

5 5 4 2
.#..#
#.###
##...
#..#.
#.###

Sample Output 3

3