Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
IMPC16 Groups Contests 36.
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
|
Для отправки решений необходимо выполнить вход.
|