시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB1000.000%

문제

Romas does not like doing cleaning, so he bought an autonomous robotic vacuum-cleaner. Unfortunately, it turns out that the robot is quite primitive – when vacuum-cleaning, it just moves straight forward until it hits an obstacle (e.g. a piece of furniture or a wall); then it turns right by 90 degrees and repeats the same.

Romas’ flat plan can be modelled by an N × M grid; each cell of the grid is a square that represents either free area (can be cleaned by the robot), or occupied (contains an obstacle). Robot moves through squares parallel to the sides of the grid.

Romas will switch the robot on before leaving to work. Upon arrival he would like to have the biggest possible area cleaned.

Find the largest possible area that the robot can clean. The robot can be started from any free square in any direction – up, down, left or right.

입력

The first row contains two integers: the dimensions of the rectangle-sized flat N and M. The N following rows describe the flat plan. Each of these rows contains M symbols that represent the state of each square:

  • . (dot) – the square is free;
  • # (hashtag) – the square is occupied.

All border squares are occupied. There will always be at least one free square.

출력

Output a single integer – the largest number of squares the robot can clean.

제한

  • 3 ≤ N, M ≤ 1 000

서브태스크

번호배점제한
17

N = 3

239

N, M ≤ 40

313

N, M ≤ 300. There will be at most 300 occupied inner1 squares.

441

None

1Squares that are not on the border of the grid.

예제 입력 1

5 6
######
###..#
#...##
#.##.#
######

예제 출력 1

4

One possible way to clean 4 squares is as follows:

  • start at (4; 2) and go up to (3; 2);
  • then it will not be able to go up, so it will turn right;
  • and will go to squares (3; 3), (3; 4);
  • after hitting the wall it will turn downwards;
  • but there also is a wall there, so further turning will steer it left;
  • and will go back to squares (3; 3), (3; 2);
  • after reaching the wall it will turn around and start going back and forth, without cleaning any additional squares.

Here is the order of squares as they will be cleaned:

######
###..#
#234##
#1##.#
######

채점 및 기타 정보

  • 예제는 채점하지 않는다.