Bubble Puzzle

시간 제한8초메모리 제한512 MB

요약

4x4 격자의 버블 상태가 주어질 때, 물방울 연쇄 반응을 고려해 모든 버블을 터뜨리는 최소 클릭 수를 구하고 5를 넘으면 -1을 출력한다.

난이도: 어려움10점 중 8점
유형: BFS, 시뮬레이션, 완전 탐색, 구현
정답자: 아직 제출이 없습니다

문제

인터넷에서 "Bubble Puzzle"이라는 브라우저 기반 퍼즐 게임이 유행하고 있다.

이 퍼즐은 4 × 4 격자에서 진행되며, 처음에 몇몇 칸에 버블이 들어 있다. 각 버블은 양의 정수로 표현되는 상태를 가지며, 자극을 받으면 상태가 변한다. 버블을 클릭하면 자극할 수 있고, 그러면 버블의 상태가 1 증가한다. 빈 칸을 클릭할 수도 있다. 이 경우 그 칸에 상태 1인 버블이 새로 생긴다.

버블의 상태가 5 이상이 되면 버블은 터져서 사라지고, 작은 물방울이 상하좌우 네 방향으로 날아간다. 물방울은 1초에 한 칸씩 움직인다. 버블이 터지는 순간 물방울 4개가 버블이 있던 칸에 있고, 1초 뒤에는 인접한 칸에 있으며, 이후에도 마찬가지다.

물방울은 버블에 부딪히거나 격자 밖으로 나가면 사라진다. 물방울이 버블에 부딪히면 그 버블의 상태가 1 증가한다. 마찬가지로 한 버블에 여러 물방울이 동시에 부딪히면, 부딪힌 물방울의 수만큼 상태가 증가한다. 물방울끼리는 충돌하지 않는다.

위 그림처럼 터져서 생긴 물방울이 다른 버블을 터뜨릴 수 있다. 즉, 한 번의 폭발이 연쇄 반응을 일으킬 수 있다. 물방울이 날아다니는 동안에는 어떤 칸도 클릭할 수 없다. 즉, 연쇄 반응이 끝날 때까지 기다려야 한다. 이 퍼즐의 목표는 모든 버블을 터뜨려 모든 칸을 비우는 것이며, 가능한 한 빠르게 끝내는 것이다.

여러분의 임무는 퍼즐을 푸는 데 필요한 최소 클릭 수를 계산하는 것이다.

입력

입력은 4줄로 이루어지며, 각 줄에는 5보다 작은 음이 아닌 정수 4개가 들어 있다. 각 정수는 격자 칸에 있는 버블의 초기 상태를 나타낸다. 0은 해당 칸이 비어 있음을 뜻한다.

출력

격자의 모든 버블을 터뜨리는 데 필요한 최소 클릭 수를 한 줄에 출력한다. 답이 5보다 크면 대신 −1을 출력한다. 출력에는 다른 문자가 들어가면 안 된다.

예제3

예제 1
입력
```
4 4 4 4
4 4 4 4
4 4 4 4
4 4 4 4
```
예상 출력
```
1
```
예제 2
입력
```
2 4 4 1
2 4 4 1
2 4 4 1
2 4 4 1
```
예상 출력
```
5
```
예제 3
입력
```
2 4 3 4
2 2 4 4
3 3 2 2
2 3 3 3
```
예상 출력
```
3
```