| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 82 | 30 | 23 | 42.593% |
구름이는 크기 $N \times N$의 정사각형의 방에 거주하고 있다. 어느 날, 구름이는 자신의 방이 방바닥에 놓여있는 물건들로 인해 매우 더럽다는 사실을 깨달았다. 하지만 방바닥의 물건들을 정리하기에는 너무 귀찮았기 때문에, 대신 방바닥에 놓인 구멍들을 활용해 물건을 모두 제거하기로 했다.
구름이의 방에 있는 물건과 방바닥에 있는 구멍은 모두 한 칸을 차지하며, 각각은 고유한 색을 가지고 있다. 구름이는 아래와 같은 시행을 반복하여 모든 물건들을 제거할 계획이다.
만사가 귀찮은 구름이는 최소한의 시행으로 모든 물건을 제거해 방을 깨끗하게 만들고 싶다. 구름이를 도와 구름이의 방의 상태가 주어질 때, 방의 모든 물건을 제거하는 최소 시행 횟수를 구해주자.
첫 번째 줄에 방의 크기를 나타내는 $N$과 색의 수를 나타내는 $M$이 공백으로 구분되어 주어진다. ($1 \leq N \leq 1 \, 000$; $1 \leq M \leq 2$)
두 번째 줄부터 $N$개의 줄에 걸쳐 구름이의 방 상태가 주어진다. 비어있는 칸은 .으로, 물건은 소문자 알파벳으로, 구멍은 대문자 알파벳으로 주어진다. 같은 색의 구멍이 없는 물건은 없으며, 구멍끼리 색이 같은 경우도 존재하지 않는다.
알파벳은 색을 나타내며, 문자 하나의 대소문자 쌍이 한 가지 색을 나타낸다. 예를 들어, A와 a는 같은 색이고, A는 구멍을 a는 물건을 나타낸다. 색상은 A와 a, 그리고 B와 b만을 사용한다.
첫 번째 줄에 모든 물건을 제거하기 위한 최소 시행 횟수를 출력하라. 만약, 시행을 반복해도 모든 물건을 제거할 수 없다면 -1을 출력하라.
4 2 abba a.bB Abbb a.a.
2
4 2 Ba.. a... ...b ..bA
-1
School > GSHS x SASA > 제1회 GSHS x SASA 프로그래밍 경시대회 B번