815. Bus Routes #

Problem #

We have a list of bus routes. Each routes[i] is a bus route that the i-th bus repeats forever. For example if routes[0] = [1, 5, 7], this means that the first bus (0-th indexed) travels in the sequence 1->5->7->1->5->7->1->… forever.

We start at bus stop S (initially not on a bus), and we want to go to bus stop T. Travelling by buses only, what is the least number of buses we must take to reach our destination? Return -1 if it is not possible.

Example:

Input: 
routes = [[1, 2, 7], [3, 6, 7]]
S = 1
T = 6
Output: 2
Explanation: 
The best strategy is take the first bus to the bus stop 7, then take the second bus to the bus stop 6.

Note:

• 1 <= routes.length <= 500.
• 1 <= routes[i].length <= 500.
• 0 <= routes[i][j] < 10 ^ 6.

Problem Summary #

We have a series of bus routes. On each route routes[i], there is a bus that travels in a loop. For example, a route routes[0] = [1, 5, 7] means the first bus (index 0) will always travel along the station route 1->5->7->1->5->7->1->…. Suppose we start at station S (initially not on a bus) and want to go to station T. During the trip we can only take buses. Find the minimum number of buses we need to take. Return -1 if it is impossible to reach the destination stop.

Notes:

• 1 <= routes.length <= 500.
• 1 <= routes[i].length <= 500.
• 0 <= routes[i][j] < 10 ^ 6.

Solution Approach #

• Given some bus routes, each route represents which stops it passes through. Now given the start and end stops, ask for the minimum number of buses needed to get from the start to the end.
• This problem can be converted into a graph theory problem: treat each stop as a vertex, and bus routes as the edges of each vertex. Edges belonging to the same bus have the same color. The problem can then be transformed into finding the minimum number of differently colored edges needed to go from vertex S to vertex T. BFS can easily solve this. Starting from S, continuously expand the stops it can reach. Use the visited array to prevent cycles caused by adding stops that are already reachable. Use a map to store the mapping relationship between stops and buses (that is, which buses can reach a certain stop). During BFS, this mapping can be used to obtain the other stop information for a bus, thereby expanding the reachable stops in the queue. Once the expansion reaches the destination T, the result can be returned.

Code #

package leetcode

func numBusesToDestination(routes [][]int, S int, T int) int {
	if S == T {
		return 0
	}
	// In vertexMap, key is a stop, value is an array of buses, indicating these bus routes can reach this stop
	vertexMap, visited, queue, res := map[int][]int{}, make([]bool, len(routes)), []int{}, 0
	for i := 0; i < len(routes); i++ {
		for _, v := range routes[i] {
			tmp := vertexMap[v]
			tmp = append(tmp, i)
			vertexMap[v] = tmp
		}
	}
	queue = append(queue, S)
	for len(queue) > 0 {
		res++
		qlen := len(queue)
		for i := 0; i < qlen; i++ {
			vertex := queue[0]
			queue = queue[1:]
			for _, bus := range vertexMap[vertex] {
				if visited[bus] == true {
					continue
				}
				visited[bus] = true
				for _, v := range routes[bus] {
					if v == T {
						return res
					}
					queue = append(queue, v)
				}
			}
		}
	}
	return -1
}