Connection Status:
Competition Arena > ExpensiveTravel

ExpensiveTravel

SRM 335 · 2007-01-17 · by soul-net

SRM 335 · 2007-01-17 · by soul-net · Graph Theory
Class Name: ExpensiveTravel
Return Type: int
Method Name: minTime
Arg Types: (vector<string>, int, int, int, int)
Problem Statement

Problem Statement

You are lost in a strange land and have to return to the base camp as soon as possible. The land is modeled as a rectangular plane divided into square cells, and each cell can be of one of 9 different types, numbered from 1 to 9. The cost of a cell of type k is exactly 1/k.

To get to the base camp, you can move from each cell to any of its orthogonally adjacent cells (up, down, left or right) instantaneously. The only limitation for the speed of your movements is the cost-per-minute. Time will be divided into one minute intervals, i.e., there is an interval starting at time 0 and ending at time 1, another interval from time 1 to time 2, etc. During each interval of time, the sum of the costs of all the cells you occupy must not exceed 1. If you make an instantaneous move at the exact boundary between two intervals of time, the cells you move between during that move will count toward both intervals' total costs. This means you can never step into or out of a cell of type 1 because any other cell you occupy will always exceed the maximum cost per minute.

You will be given m, a String[] describing the land, where the jth character of the ith element represents the type of the cell at row i, column j (both 1-based). You will also be given startRow, startCol, endRow and endCol, the 1-based indices of the row and column of your starting point and destination, respectively. Return the minimum number of minutes that are needed to get from (startRow, startCol) to (endRow, endCol) following the constraints above. If it's impossible to do so, return -1.

Constraints

  • m will contain between 1 and 50 elements, inclusive.
  • Each element of m will contain exactly N characters, where N is an integer between 1 and 50, inclusive.
  • Each character of each element of m will be a digit between '1' and '9', inclusive.
  • startRow and endRow will each be between 1 and the number of elements in m, inclusive.
  • startCol and endCol will each be between 1 and the number of characters in the first element of m, inclusive.
  • Either startCol will be different from endCol or startRow will be different from endRow.
Examples
0)
{"22334"}
1
1
1
5
Returns: 3

During the first minute, you can move 1 cell to the right. The two cells that you occupy during that minute are both of type 2, so the cost is 1/2+1/2=1. In the second minute, you can move 1 more cell to the right. You cannot go any further because 1/2+1/3+1/3 > 1. During the third minute, you can reach your destination by moving 2 cells to the right for a cost of 1/3+1/3+1/4 < 1.

1)
{"55",
 "52",
 "55"}
1
2
3
2
Returns: 1

You can step on all 5 5's during the same interval, so you can get there in just 1 minute.

2)
{"251",
 "212",
 "122"}
1
1
3
3
Returns: -1

Since it's impossible to step into a cell of type 1, there is no way to get to your destination.

3)
{"452232",
 "287979",
 "219872",
 "928234",
 "767676"}
1
6
3
1
Returns: 3
4)
{"11"}
1
1
1
2
Returns: -1

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

Coding Area

Language: C++17 · define a public class ExpensiveTravel with a public method int minTime(vector<string> m, int startRow, int startCol, int endRow, int endCol) · 105 test cases · 2 s / 256 MB per case

Submitting as anonymous