시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 159 19 15 10.870%

문제

파인애플은 열대과일로, 잘 자라기 위해서 많은 비가 필요하다. 병찬이는 피자에 파인애플을 더 많이 넣기 위하여 비가 많이 오는 열대지역에 산을 통째로 구입했다.

병찬이는 모든 땅에 파인애플을 심어 자라게 하려 하는데, 문제가 발생했다. 비가 너무 많이 오게 되면 산에 거대한 물웅덩이가 생길 수 있는데, 파인애플이 물에 빠지면 재배를 할 수가 없다. 그래서 병찬이는 이 산에서 가장 큰 웅덩이를 찾고 싶다.

다음 조건을 만족하는 영역을 웅덩이라고 한다.

  1. 산은 가로 W, 세로 H 의 칸들로 구성되며, 각 칸의 높이는 1이상 109 이하의 정수다. 이 산 바깥의 모든 높이는 0이라고 가정한다.
  2. 한 웅덩이의 각 칸들은 연결되어 있다. 이때 연결되어 있다는 것은 칸들이 서로 상하좌우 넷 중 하나로 인접하다는 것을 의미하며, 대각선으로 나열된 칸은 연결된 것이 아니다.
  3. 다음 조건을 만족하는 h가 존재한다.
    • 웅덩이의 모든 칸의 높이는 h 이하이다.
    • 웅덩이와 상하좌우로 연결되어 있는, 웅덩이가 아닌 모든 칸의 높이는 h + 1 이상이다.

입력

첫 번째 줄에는 병찬이가 구입한 산의 세로 크기 H와 가로 크기 W가 주어진다. (1 ≤ W, H ≤ 1,000)

두 번째 줄부터 H + 1번째 줄까지 각 줄마다 W개의 수가 주어진다.

i + 1(1 ≤ i ≤ H)번째 줄의 j번째 수는 산의 i행 j열 부분의 높이를 의미한다.

출력

이 산에 존재하는 가장 큰 웅덩이의 크기를 출력한다. 웅덩이가 없을 경우 0을 출력한다.

예제 입력 1

5 5
8 7 6 6 8
9 8 5 4 9
7 2 3 7 5
9 5 6 2 3
9 9 6 4 1

예제 출력 1

5

힌트

회색으로 칠한 부분이 최대 크기의 웅덩이다.

8 7 6 6 8
9 8 5 4 9
7 2 3 7 5
9 5 6 2 3
9 9 6 4 1

출처

University > POSTECH > PPC 2018 B번

  • 데이터를 추가한 사람: doju
  • 문제를 만든 사람: hyperbolic