Willy the Worm is crawling through a 5x5 grid. The squares in the grid are
numbered 0 through 24, from left to right, top to bottom:
0 1 2 3 4
5 6 7 8 9
10 11 12 13 14
15 16 17 18 19
20 21 22 23 24
Some of the squares contain obstacles.
What is the maximum number of squares Willy can visit before he gets stuck?
Willy travels through the grid as follows:
-He always starts on square 0, going either down or right.
-He can move in four directions: up, down, left, right.
-He cannot travel through:
(a) an obstacle
(b) a square he has previously visited
-He moves in a straight line until he reaches a square he can not travel
through or the edge.
-When he cannot move straight, he turns either left or right.
-When he cannot move left, right, or straight, he stops.
Implement a class Obstacle, which contains a method getLongestPath.
getLongestPath is passed an int[] of elements that are the squares which have
obstacles in them, and returns an int that is the maximum number of squares
Willy can visit before he stops.
Examples:
-If the obstacles int[] is {4,12,15,23}, the longest path Willy can travel is:
0->5->10->11->16->21->22->17->18->19->14->9->8->7->6->1->2->3
In this path, Willy travels through 18 squares, so the method should return 18.
-If obstacles is {4,10,11,12,14}, the method should return 14
The method signature is:
public int getLongestPath(int[] obstacles);
obstacles is an int[] of elements between 1 and 24, inclusive (0 can not
contain an obstacle).
Note:
-Your algorithm must run in under 6 seconds.
-If Willy cannot move anywhere to start (obstacles on squares 1 and 5), he has
still visited square 0 and the method should return 1.
|