TopCoder problem "MountainWalk" used in SRM 394 (Division II Level One)



Problem Statement

    You are in a mountainous area which is represented by a String[] areaMap. The j-th character of the i-th element of the areaMap is a digit '0'-'9' representing the height of cell (i, j). You perform a walk in the area according to the following rules:
  • You start from cell (0, 0).
  • If you are in cell (i, j), you examine cells (i+1, j), (i, j-1), (i-1, j), (i, j+1) in this order. You go to the first of these cells you can enter. You can enter a cell if it is still on the map, you haven't been to it before and the difference between the heights of your current cell and the cell you want to enter is no bigger (in absolute value) than heightDifference.
  • You end your walk if you can not make another move, i.e., if you can not enter any neighboring cell.
You must return the number of cells that you visit while performing your walk. You visit cell (i, j) if and only if you enter cell (i, j) at some point during your walk (the starting cell (0, 0) also counts as entered, i.e., you definitely visit (0, 0)). Note that you will visit each cell at most once since you never enter the same cell twice.
 

Definition

    
Class:MountainWalk
Method:cellsVisited
Parameters:String[], int
Returns:int
Method signature:int cellsVisited(String[] areaMap, int heightDifference)
(be sure your method is public)
    
 

Constraints

-areaMap will contain between 1 and 50 elements, inclusive.
-All the elements of areaMap will contain the same number of characters.
-Each element of areaMap will contain between 1 and 50 digits ('0' - '9'), inclusive.
-heightDifference will be between 0 and 9, inclusive.
 

Examples

0)
    
{"056",
 "135",
 "234"}
1
Returns: 5
Your path goes (0, 0) --> (1, 0) --> (2, 0) --> (2, 1) --> (1, 1) and so you visit 5 cells.
1)
    
{"056",
 "195",
 "234"}
1
Returns: 8
Now you can not enter the cell (1, 1) because of the cell difference so your path goes (0, 0) --> (1, 0) --> (2, 0) --> (2, 1) --> (2, 2) --> (1, 2) --> (0, 2) --> (0, 1).
2)
    
{"865",
 "123",
 "111"}
3
Returns: 9
Your path is (0, 0) --> (0, 1) --> (0, 2) --> (1, 2) --> (2, 2) --> (2, 1) --> (2, 0) --> (1, 0) --> (1, 1).
3)
    
{"00009876543210",
 "00009876543210",
 "00009876543210",
 "00009876543210"}
8
Returns: 16
4)
    
{"0000",
 "0000",
 "0000",
 "0000",
 "9999",
 "8888",
 "7777",
 "6666",
 "5555",
 "4444",
 "3333",
 "2222",
 "1111",
 "0000"}
3
Returns: 16
5)
    
{"173642855131893831828253420",
 "126290035950506994475683704",
 "381277675415026563959463393",
 "019782700912864681764582260",
 "496448425114634806770407597",
 "049628433145840178727435051",
 "117194708226266248973780562",
 "398138380998246682323622510",
 "408178777661559971959512111"}
8
Returns: 135
6)
    
{"9"}
0
Returns: 1

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8734

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=11128&pm=8734

Writer:

Xixas

Testers:

PabloGilberto , Olexiy , marek.cygan , ivan_metelsky

Problem categories:

Simulation