TopCoder problem "DesertWind" used in SRM 164 (Division I Level Three)

Problem Statement

    The Desert. Failing water, dying camels, howling wind. The desert wind has hands -- it throws sand in your face, pushes you down, tries to bury you.

We are stranded in the desert. But we have a map showing where we are, where all the impassable terrain is located, and where every oasis is located. The map is divided into square cells, and our trip will be a sequence of legs, where each leg goes from one cell to one of the 8 adjacent cells. We must start at our current location and make it to an oasis, any oasis. Of course, we cannot use any impassable cell and cannot leave the mapped area. Our survival depends on how many days it will take to make the journey.

That evil Desert Wind is our nemesis! Each leg takes one day unless we are traveling directly against the wind. In that case the leg will take three days. Fortunately, the wind's direction can be determined just before setting out on a leg and will not change for at least a day.

Create a class DesertWind that contains the method daysNeeded that takes a String[] theMap and returns the number of days required, assuming the worst possible wind conditions will occur. Return -1 if no path to an oasis exists.

Each element of theMap gives the terrain for the cells (in west to east order) at a particular latitude; the first element is the most northern, the last element is the most southern on the map. Each cell is indicated by a single character:

  • '*' is an oasis
  • 'X' is impassable
  • '@' is the starting location
  • '-' is sand



Method signature:int daysNeeded(String[] theMap)
(be sure your method is public)


-theMap has between 2 and 50 elements inclusive, each having the same length
-the length of each element of theMap is between 2 and 50 inclusive
-'@' appears exactly once in exactly one element of theMap
-each element of theMap contains only the characters '*','-','X','@'


Returns: 2
   - - *
   @ - *
   X - -
No matter how the wind is blowing we can make it to one of the two northernmost cells in the second column in one day. Whichever cell we reach and whichever way the wind is blowing the second day, we can get to an oasis without heading into the wind.
Returns: 3
   - X - *
   - @ X -
   - - - X
   - - * *
Unless the wind is from the southeast, we will go southeast on the first day, and then will have two different directions that lead to an oasis -- one of them will not be against the wind so we will reach an oasis in 2 days. But if the wind is from the southeast on the first day, we will go south. Then, if the wind is from the southeast on the second day we will go east (otherwise we can go southeast to an oasis). Now we can reach one of the two oases on the third day, no matter how the wind blows.

There is no way to reach the northeast oasis in less than 4 days if the wind is evil. Even if the first day the wind is not from the northeast, it would be a fatal mistake to go that direction.

Returns: -1

Problem url:

Problem stats url:




lbackstrom , brett1479

Problem categories:

Dynamic Programming, Graph Theory