IMPC17 Prep Contest |
Start: Apr.22.2017 at 02:00:00 PM
Finish: Apr.22.2017 at 07:00:00 PM
The contest is finished!
• Contest scoreboard
|
Feedback | If you notice incorrect translations in Contester, please let author know.
|
|
Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb. Question by Ibrahim Mesecan.
Minimum
time to exit building
Question:
Police is running after a thief who is trying to
escape out of a building. Because, he wants to
go out of a high building, he goes only down, left,
or right to the rooms which he did not visit before.
There are obstacles in the rooms which slows him down.
The number in every cell represents the
amount of time required to pass from the room.
And, he searches the fastest way (the path with the
smallest total value). Write a program that finds
the path with the smallest value.
Input specification:
Firstly, you will be given two integers (n and m)
where n is the size of 2D square matrix and m is
the starting column from the top row. Then, in
the following n lines you will be given n integers
where 1 ≤ (n and m) ≤ 20 and the numbers
in the matrix are less than 1001.
Output specification:
Show one integer: the total time required
to go out of building.
Sample Input |
Sample Output |
4 1
6 5 7 9
10 3 1 7
2 7 4 2
8 8 1 2
|
20
|
Explanation:
He starts from the first column. Then,
he can follow the path
6 + 5 + 3 + 1 + 4 + 1 = 20
Для отправки решений необходимо выполнить вход.
|