3082번 - 아름다운 제도 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 68 | 7 | 7 | 20.000% |
문제
상근이가 살고 있는 나라는 매우 많은 섬으로 이루어져 있다. 이 나라의 국민들은 나라가 매우 많은 섬으로 이루어져 있다는 사실을 자랑스러워 하고 있다.
나라를 이루고 있는 섬 중 일부는 같은 모양이다. 한 섬을 이동시켜서 다른 섬과 완전히 일치하게 만들 수 있다면, 두 섬을 같은 모양이라고 한다. 이러한 사실 때문에, 많은 관광객은 나라의 아름다움을 측정한다. 나라의 아름다움이란 같은 모양을 가지는 섬의 쌍의 개수와 같다.
하지만, 지구 온난화 때문에 해수면은 매년 상승하고 있다. 해수면의 상승은 아름다움을 매년 변하게 만든다.
이 나라의 지도는 R×C개의 정사각형으로 나타낼 수 있다. 지도를 만든 시점에 해수면은 0이며, 섬의 높이는 모두 자연수이다. 해수면은 1년에 1씩 상승한다. T년이 지난 후에, T보다 낮은 높이를 가진 섬은 모두 물에 잠기게 된다. 섬을 이루고 있는 돌은 모두 구멍이 많다. 따라서, T보다 높이가 낮으면서 섬의 내부에 있는 곳도 모두 물에 잠기게 된다. 두 땅(정사각형)이 같은 섬에 포함되려면, 한 땅에서 출발해서 그 땅으로 왼쪽, 오른쪽, 위, 아래쪽 땅으로만 지나가서 도착할 수 있어야 한다.
| 초기 상태 | 5년 후 |
T년이 지난 후에 이 나라의 아름다움이 어떻게 변하는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 지도의 크기 R과 C가 주어진다. (3 ≤ R, C ≤ 1000)
다음 R개 줄에는 C개의 음이 아닌 정수가 주어진다. 정수는 공백으로 구분되어져 있다. 각 값은 109를 넘지 않고, 측정할 당시에 그 땅의 높이를 나타낸다.
다음 줄에는 조사하려고 하는 연도의 수 Q가 주어진다. (1 ≤ Q ≤ 100 000)
다음 줄에는 Q개의 자연수가 공백으로 구분되어 주어지며, 모두 109를 넘지 않는다. 입력으로 주어진 값에 따라서 그 해가 지나면 아름다움이 어떻게 변하는지를 출력한다. 연도는 오름차순으로 주어진다.
출력
총 Q개 줄에 걸쳐서, 입력으로 주어진 해만큼 지나면 나라의 아름다움이 몇 인지를 출력한다.
예제 입력 1
5 6 100 2 3 4 5 6 20 4 45 12 3 4 0 0 1 2 3 0 0 0 0 0 0 0 0 0 1 2 3 0 3 1 4 10
예제 출력 1
0 1 0
예제 입력 2
7 6 5 8 0 9 7 6 7 0 0 9 2 6 8 0 6 7 9 7 0 0 8 7 0 0 0 5 0 0 3 2 0 9 0 0 6 0 8 1 0 0 7 0 1 5
예제 출력 2
4
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호