HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Contests > IMPC17 Prep Contest > problem:


4. 51100 - Minimum time to exit building

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

Guest
• Review clarifications (1)

Contest problems

• 1. 51099 - Mr. Monk
• 2. 51098 - Rotate a matrix
• 3. 51097 - Sum of Borders
• 4. 51100 - Minimum time to exit...
• 5. 50621 - Postal Figures

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



Для отправки решений необходимо выполнить вход.

www.contester.ru