문제
정올이는 애벌레를 키우기 위해 N * N개의 격자 모양으로 애벌레 집을 만들어 놓았다.
애벌레가 먹을 수 있는 먹이를 모두 먹는데 걸리는 시간을 구하는 프로그램을 작성하라.
그리고 격자의 여러 곳에 M개의 먹이를 뿌려 놓았다.
즉 한칸에는 최대 1개의 먹이가 놓여 있다.
먹이는 크기가 서로 다르기 때문에 크기를 기준으로 1부터 8까지의 자연수로 표시가 되어 있다.
애벌레의 크기는 처음에 2이고 자신보다 크기가 작은 먹이만을 먹을 수 있다.
자신의 크기만큼 먹이를 먹게되면 크기가 1씩 증가하게 된다.
즉 크기가 1인 먹이를 2개 먹고 나면 애벌레의 크기는 3이 되고 이후 크기가 1 또는 2인 먹이를 3개 먹고나면 애벌레의 크기는 4가 된다.
애벌레는 상하좌우로 한 칸씩 이동을 할 수 있지만 범위를 벗어나거나 자신보다 큰 먹이가 있는 곳으로는 이동을 할 수 없다.
자신과 크기가 같은 먹이가 있다면 이동은 가능하지만 먹이를 먹을 수는 없다.
애벌레가 한칸을 이동하는 데에는 1분이 걸리고 애벌레는 가장 빨리 먹을 수 있는 먹이부터 먹는다.
가장 빨리 먹을 수 있는 먹이가 여러개 있다면 행번호가 작은 것, 행번호도 같다면 열번호가 작은것을 먼저 먹는다.
입력
첫째 줄에 애벌레의 집의 한변의 길이 N(2 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 N개의 정수로 구성된 애벌레 집의 정보가 주어진다.
각 정수가 나타내는 의미는 다음과 같다.
- 0: 빈 칸
- 1 ~ 8 : 칸에 있는 먹이의 크기
- 9 : 애벌레의 처음 위치
애벌레는 공간에 오직 한 마리 뿐이다.
출력
첫째 줄에 주어진 순서대로 먹을 수 있는 먹이를 모두 먹을때 까지의 시간을 출력한다.
예제
4
4 3 2 1
0 0 0 0
0 0 9 0
1 2 3 4
14
힌트
로그인해야 코드를 작성할 수 있어요.