Connection Status:
Competition Arena > DrivingAround

DrivingAround

SRM 342 · 2007-03-14 · by Kawigi

SRM 342 · 2007-03-14 · by Kawigi · Graph Theory, Simulation
Class Name: DrivingAround
Return Type: int
Method Name: numberOfWays
Arg Types: (vector<string>, int, int, int)
Problem Statement

Problem Statement

You are picking up your friend from the airport, and you just got a call - your friend's flight was delayed! You know exactly how long it will be in minutes before your friend will be ready to get picked up, and you want to drive around until that point in time, arriving at the airport at exactly that time. You want to find out how many ways there are to reach the airport in exactly that amount of time.

The city layout is given as a String[] adj. The ith character of the jth element of adj is '.' if there is no road connecting intersection i to intersection j (both zero-indexed). If there is a road from intersection i to intersection j, the number of minutes it takes to travel that road is given as a number from '1' to '5'. Roads are not necessarily two-way, and two-way roads may not be the same speed both ways. You are at intersection start when you get your friend's call, and the airport is at intersection finish. Calculate the number of ways to get from intersection start to intersection finish in exactly time minutes. Since this number might be rather large, return the answer modulo 1000003.

Constraints

  • adj will contain between 1 and 10 elements, inclusive.
  • The number of characters in each element of adj will be the same as the number of elements in adj.
  • Each character in adj will be a '.' or a digit between '1' and '5', inclusive.
  • start and finish will each be between 0 and n-1, inclusive, where n is the number of elements in adj.
  • The ith character of the ith element of adj will be '.', for all i.
  • time will be between 1 and 1000000000, inclusive.
Examples
0)
{".12",
 "2.1",
 "12."}
0
2
5
Returns: 8

There are 8 ways: 0->1->2->0->1->2 0->1->2->0->2 0->1->2->1->2 0->1->0->1->2 0->1->0->2 0->2->0->1->2 0->2->1->2 0->2->0->2

1)
{"....52....",
 "..5.......",
 "..........",
 ".......1..",
 "......42.2",
 "5...4.....",
 ".5...4...1",
 "......5...",
 ".3244.....",
 ".........."}
2
2
10
Returns: 0
2)
{"...14....1",
 "......13..",
 ".2...4....",
 "....52.5..",
 "1.3..4....",
 ".3....35.5",
 "4......1.1",
 "..4.4.1.54",
 "....4.11.5",
 "31144.2.4."}
7
2
100
Returns: 316984
3)
{"...43..4.4", "......1.3.", ".5......4.", "34.......2", "..........", "........1.", "35.......4", "....2.2..4", "5...5..5..", "1....2..4."}
5
5
10000
Returns: 28404
4)
{".....3.25.", "..3...3533", ".5.421.22.", "42....3121", "5421.1.114", "1.5.1.513.", "..513..5.1", "2.14142..4", "5.334333.1", "1....5.44."}
6
4
10000000
Returns: 863687

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

Coding Area

Language: C++17 · define a public class DrivingAround with a public method int numberOfWays(vector<string> adj, int start, int finish, int time) · 99 test cases · 2 s / 256 MB per case

Submitting as anonymous