키오스크 설치

면접 대비

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

요약

탐욕적 이동 규칙으로 모든 칸에 닿는 키오스크 칸을 찾아 그 칸의 최대 이동 거리를 구하고, 없으면 impossible을 출력합니다.

난이도: 보통10점 중 5점
유형: 그래프, BFS, 구현
정답자: 아직 제출이 없습니다

문제

여러분은 Beautifully Arranged Placid Camping을 열려고 한다. 땅은 이미 샀고, 이를 $h \times w$ 격자 구역으로 나누었다. 각 구역에는 1부터 $h \cdot w$ 까지의 서로 다른 번호 $a_{ij}$ 가 붙어 있다.

아직 정하지 않은 것이 하나 있다. 접수 키오스크를 구역 중 한 곳에 놓아야 한다. 방문객이 키오스크에서 자기 구역까지 걷는 최대 거리를 가능한 한 줄이고 싶다.

방문객은 최단 경로로 걷지 않는다. 키오스크에서 출발해 다음 절차를 따른다.

인접한 네 구역의 번호를 확인한다.
번호가 목적지 번호에 가장 가까운 구역으로 간다. 두 구역이 동점이면 현재 구역 번호에 더 가까운 번호의 구역으로 간다.
목적지에 도착할 때까지 반복한다.

이 절차는 끝나지 않을 수도 있다.

그림 K.1은 해를 하나 보여 준다. 키오스크를 4번 구역에 두면 다른 모든 구역이 최대 거리 3 이내에 있다. 7번 구역에 두면 9번 구역에 도달하지 못한다.

입력

첫 줄에 격자의 크기인 두 정수 $h$ 와 $w$ 가 주어진다 ( $2 \leq h, w \leq 40$ ).

이어서 $h$ 개의 줄이 주어진다. $i$ 번째 줄에는 $w$ 개의 정수 $a_{i,1}, \ldots, a_{i,w}$ 가 주어진다. 구역 번호이며 ( $1 \leq a_{i,j} \leq h \cdot w$ ), 1부터 $h \cdot w$ 까지의 모든 수가 정확히 한 번씩 나타난다.

출력

모든 구역에 도달할 수 있는 구역이 있으면, 그 구역의 번호와 그곳에서 가장 먼 구역까지의 도보 거리를 출력한다. 어느 구역에 키오스크를 두어도 도달하지 못하는 구역이 하나 이상 있으면 impossible을 출력한다.

해가 여럿이면 그중 아무 것이나 출력해도 된다.

예제3

예제 1
입력
```
2 3
1 2 3
6 5 4
```
예상 출력
```
2 2
```
예제 2
입력
```
3 3
1 4 8
7 5 2
3 9 6
```
예상 출력
```
impossible
```
예제 3
입력
```
3 3
9 3 1
4 7 2
8 6 5
```
예상 출력
```
4 3
```