경완이와 진욱이는 학교에서 수업을 들은 뒤 점심을 먹으러 나갔다.

학교는 가로 n칸 세로 n칸으로 이루어져 있으며 이 중 몇몇 칸에는 건물이 있어 이동할 수 없다.

아래 그림 1에서 회색으로 표시된 부분이 건물 빨간색으로 표시된 부분이 출발점 파란색으로 표시된 부분이 도착점이다.

건물과 출발점 도착점을 제외한 모든 칸에는 일사량이 자연수로 주어져 있다.

밖의 날씨가 매우 덥기 때문에 경완이와 진욱이는 일사량들의 합이 최소가 되는 경로로 이동하려고 한다.

예를 들어 그림 2와 같이 이동하면 일사량의 합이 23이지만 그림 3과 같이 이동하면 일사량의 합이 14로 최소가 된다.

그런데 식당은 t분 후에 문을 닫으므로 경완이와 진욱이는 t분 내로 식당에 도착해야한다.

단 격자 1칸을 이동하는 데는 1분이 걸린다. 그러므로 위 그림 2와 같이 이동하는 데는 6분 그림 3과 같이 이동하는 데는 10분이 걸린다.

만약 t = 9라면 그림 3과 같이 이동할 수 없으며 따라서 그림 4의 경로를 선택하는 것이 일사량 최소로 한다.

학교의 크기 n과 각 칸에서의 일사량과 시간 t가 주어졌을 때 시간 내로 이동할 수 있으면서 일사량들의 합을 최소로 하는 프로그램을 작성하여라.

경로찾기(find route) timer 1s memory 128MB

경로찾기(find route) 1s 128MB