TopCoder problem "DrivingAround" used in SRM 342 (Division I Level Three)



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.

 

Definition

    
Class:DrivingAround
Method:numberOfWays
Parameters:String[], int, int, int
Returns:int
Method signature:int numberOfWays(String[] adj, int start, int finish, int time)
(be sure your method is public)
    
 

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

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10666&pm=7412

Writer:

Kawigi

Testers:

PabloGilberto , brett1479 , Cosmin.ro , Olexiy

Problem categories:

Graph Theory, Simulation