HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Dynamic programming & Greedy > problem:


50930 - Tom and Jerry

Guest
• Review clarifications (1)

Section problems

• 50979 - Minimum access cost for BST
• 50688 - Epoka Furgon
• 50689 - The biggest building block
• 50686 - The Container
• 50524 - Elevator
• 50536 - Epoka Furgon Shpk
• 50682 - Hotel Durres
• 50526 - Gold Market
• 50930 - Tom and Jerry
• 50488 - Connecting Wires
• 50842 - Minimum Sum Triangle - DP
• 50676 - Cinema Millennium
• 50678 - The Jumping Rabbit
• 50598 - Minimum Sum
• 50683 - Parking Buses
• 50685 - Guest Room Usage
• 50674 - Collecting Eggs

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.

Tom And Jerry

Poor mouse Jerry is stuck in a maze. He wants to reach the cheese. But there are walls which Jerry cannot pass through and Tom has placed needles and such other stuff around which hurts Jerry. So, too many needles may kill him and he wants to avoid as much as he can. Jerry always starts from the upper left corner and the cheese is always at the bottom right corner.

Question: Write a program, that finds the path which hurts him the least and reaches to the destination.

Input specification
You will be given an integer in the beginning: the size of square matrix (n) where 0 ≤ n ≤ 100. Then, in the following n lines you will be given n integers where positive numbers represent the number of needles (more needles hurt more). The negative numbers represent the walls.

Output specification:
If there is no path to the cheese show minus one (-1). If there is a path show the minimum cost to the cheese.

Sample Input I
5
1 3 4 0 4
2 2 0 -1 -1
0 -1 0 3 0
0 -1 1 0 2
1 0 2 -1 0
Sample Output I
8



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

www.contester.ru