Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
Question by Ibrahim Mesecan.
The Longest Path
Question:
There is snake moving around the maze. And, it wants to travel
as long as possible. The snake can use the same direction it
currently has or it can change direction according to the values
of the cells. The cell value is 0 means no change in direction.
If there is number in the cell, the snake uses the cell value
modulus 4 to decide for the new direction. The table on the
right gives possible directions according to the value of
the cell. So, the snake either keeps the current direction
or changes the direction according to the given table.
The journey ends if the snake hits to the border, or it
hits to a visited cell. The default starting direction
is Right.
Question: Write a program that defines
the length of the longest path according to the given
maze information.
Input specification:
You will be given 3 integers in the beginning,
the length of the square field (n) and the (x,y)
coordinate of the starting position. Then you
will be given a n-by-n matrix of integers where
integers are between 0 and 1000 (mostly zeros)
and 1 ≤ n ≤ 15.
Output specification:
Show one integer.
Sample Input I
4 1 1
6 0 6 0
0 0 9 0
0 0 0 0
0 0 0 0
|
Sample Input II
4 1 1
6 0 6 6
0 0 9 0
0 0 0 0
0 0 0 0
|
Sample Output I
6
|
Sample Output II
7
|
Explanation: Figure on the right,
gives 4 possible paths for the question where Path
in image (D) has the longest path (6).
Для отправки решений необходимо выполнить вход.
|