IMPC17 Prep Contest |
Старт: 22.апр.2017 в 14:00:00
Финиш: 22.апр.2017 в 19:00:00
Турнир завершён!
• Турнирная таблица
|
|
Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб. 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
Для отправки решений необходимо выполнить вход.
|