TopCoder problem "Obstacle" used in SRM 2 (Division I Level Three , Division II Level Three)

Problem Statement

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.

-If the obstacles int[] is {4,12,15,23}, the longest path Willy can travel is:
 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).

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


Method signature:int getLongestPath(int[] param0)
(be sure your method is public)

Problem url:

Problem stats url:




Problem categories: