정올국 광장에서는 자동 주행 택시를 시연할 예정이다.

광장은 n*m 격자판 모양의 직사각형 형태로 되어있으며,

각 행은 1부터 n까지, 각 열은 1부터 m까지 번호가 붙어 있다.

자동 주행 택시는 격자판의 각 칸 사이를 이동하며,

현재 위치한 칸에서 인접한 면이 존재하는 칸으로 단번에 이동할 수 있다.

올해 겨울은 눈이 많이 내려, 시연 기간 동안 무인 제설기를 이용하여 광장을 청소한다.

시연 내내 눈이 계속 내리자, 자동 주행 택시는 쌓인 눈을 극복하는 능력 또한 시연하기로 하였다.

각 격자판에 쌓인 눈의 깊이는 음이 아닌 정수로 나타낼 수 있다.

또한, 택시의 눈 극복력 또한 음이 아닌 정수로 주어진다.

택시는 이동 도중, 눈의 깊이가 택시의 눈 극복력을 넘지 않는 칸에만 있을 수 있다.

처음에는 모든 칸에 쌓인 눈의 깊이가 0이다.

매 시간이 시작할 때, 각 칸의 눈 깊이는 전부 1씩 증가한다.

이후, 세 가지 작업 중 하나가 수행된다.

각 작업에는 정확히 1시간이 걸린다.

1. 무인 제설기가 어떤 행을 청소하여, 해당 행의 모든 칸에 쌓인 눈의 깊이가 0이 된다.

2. 무인 제설기가 어떤 열을 청소하여, 해당 열의 모든 칸에 쌓인 눈의 깊이가 0이 된다.

3. 자동 주행 택시를 시연한다. 택시의 눈 극복력의 값을 설정하고, 시작 및 목적지 칸을 선택하고, 택시를 운행해 본다.

시작 칸부터 목적지 칸까지 모든 칸에 쌓인 눈의 높이가 택시의 눈 극복력 이하일 경우에만 택시가 해당 경로로 이동할 수 있다.

택시는 가장 짧은 경로로 이동한다.

각 3번 작업에 대하여, 택시 시연이 가능한지, 가능하다면 이동에 걸리는 가장 짧은 거리를 구하라.

자동 주행 택시 timer 3s memory 512MB

자동 주행 택시 3s 512MB