Connection Status:
Competition Arena > MountainWalk

MountainWalk

SRM 394 · 2008-03-22 · by Xixas

SRM 394 · 2008-03-22 · by Xixas · Simulation
Class Name: MountainWalk
Return Type: int
Method Name: cellsVisited
Arg Types: (vector<string>, int)
Problem Statement

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.

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.

Statement by TopCoder, Inc. — view the original on the archive.

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)
{"111111111111111111111111111191",
 "222222222222222222222222222282",
 "333333333333333333333333333373"}
4
Returns: 84
4)
{"00009876543210",
 "00009876543210",
 "00009876543210",
 "00009876543210"}
8
Returns: 16

Submissions are judged against all 74 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class MountainWalk with a public method int cellsVisited(vector<string> areaMap, int heightDifference) · 74 test cases · 2 s / 256 MB per case

Submitting as anonymous