레이팅 미적용베시는 관광을 좋아하는데, 오늘은 경치 좋은 골짜기를 찾고 있다.
관심 대상은 \(N \times N\) 격자의 칸들로, 각 칸에는 높이가 있다. 이 정사각형 격자 밖의 모든 칸은 무한한 높이를 갖는 것으로 간주할 수 있다.
골짜기란 이 격자에서 연결되어 있고 구멍이 없으며, 바로 둘러싸는 모든 칸이 영역 안의 모든 칸보다 높은 영역을 말한다.
더 형식적으로:
- 칸들의 집합에서 임의의 칸에서 다른 임의의 칸으로 상, 하, 좌, 우 이동의 나열로 도달할 수 있으면 그 집합을 "변 연결(edgewise-contiguous)"이라고 한다.
- 칸들의 집합에서 임의의 칸에서 다른 임의의 칸으로 상, 하, 좌, 우 또는 대각선 이동의 나열로 도달할 수 있으면 그 집합을 "점 연결(pointwise-contiguous)"이라고 한다.
- "영역"이란 비어 있지 않은 변 연결인 칸들의 집합이다.
- 영역의 여집합(\(N \times N\) 격자 밖의 무한 칸들을 포함)이 점 연결이 아니면 그 영역을 "구멍 있는(holey)" 영역이라고 한다.
- 영역의 "경계"란 영역 안의 어떤 칸과 직교로(상, 하, 좌, 우) 인접하지만 영역 자체에는 속하지 않는 칸들의 집합이다.
- "골짜기"란 영역 안의 모든 칸의 높이가 영역 경계 위의 모든 칸의 높이보다 낮은, 구멍 없는 임의의 영역이다.
베시의 목표는 모든 골짜기의 크기의 합을 구하는 것이다.
문제 제공: Travis Hance
예시
다음은 영역이다:
oo.
ooo
..o
다음은 영역이 아니다(가운데 칸과 오른쪽 아래 칸이 변 연결이 아니다):
oo.
oo.
..o
다음은 구멍 없는 영역이다:
ooo
o..
o..
다음은 구멍 있는 영역이다("도넛" 모양 안의 한 칸이 영역 "바깥"과 점 연결이 아니다):
ooo
o.o
ooo
다음은 또 다른 구멍 없는 영역이다(가운데의 한 칸이 오른쪽 아래 모서리의 칸과 점 연결이다):
ooo
o.o
oo.
문제 제공: Travis Hance
첫째 줄에 정수 \(N\)이 주어지며, \(1 \le N \le 750\)이다.
다음 \(N\)개의 줄 각각에는 격자 칸들의 높이인 \(N\)개의 정수가 주어진다. 각 높이 \(h\)는 \(1 \le h \le 10^6\)을 만족한다. 모든 높이는 서로 다른 정수이다.
적어도 19%의 테스트 케이스에서는 추가로 \(N \leq 100\)이 보장된다.
모든 골짜기의 크기의 합을 나타내는 정수 하나를 출력한다.
valleys.in · 출력을 쓸 파일 valleys.out3
1 10 2
20 100 30
3 11 5030In this example, there are three valleys of size 1:
o.o
...
o..
One valley of size 2:
...
...
oo.
One valley of size 3:
ooo
...
...
One valley of size 6:
ooo
o..
oo.
One valley of size 7:
ooo
o.o
oo.
And one valley of size 9:
ooo
ooo
ooo
Thus, the answer is 1 + 1 + 1 + 2 + 3 + 6 + 7 + 9 = 30.
riseoj 작성
출처 올림피아드 > USACO > 2018-2019 > US Open > Platinum