HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Linear Data Structures: Arrays > problem:


51061 - The Longest Path

Guest
• Review clarifications (8)

Section problems

• 50444 - n digit kth number divisible...
• 50865 - Apartment Building Adminis...
• 50874 - Apartment Building Adminis...
• 51127 - Maze solver
• 51126 - Dr. Fllanxha
• 51021 - Number of Nodes
• 51044 - Number of Trees
• 51098 - Rotate a matrix
• 51061 - The Longest Path
• 51083 - Grades Histogram
• 51084 - Reflect a matrix
• 51011 - Decoding the Path
• 51088 - Number of letters
• 51172 - The biggest Minute
• 51125 - Filling an Array 3
• 51085 - xyx Divisible by k
• 51087 - Are they the same?

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.

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).



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

www.contester.ru