Robot

시간 제한1초메모리 제한1024 MB

요약
로봇은 막힐 때까지 직진하다가 오른쪽으로 90도 회전한다. 시작 칸과 방향을 자유롭게 정할 때 청소하는 서로 다른 빈 칸 수의 최댓값을 구한다.
난이도

보통10점 중 7점

유형
시뮬레이션, 그래프, 구현, 완전 탐색
정답자
아직 제출이 없습니다

문제

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

예제1

  1. 예제 1

    입력
    5 6
######
###..#
#...##
#.##.#
######
    예상 출력
    4