Count Routes Through Four Shop Types
Problem statement
A town has shops.length shops. Shop i has type shops[i], where the four types are numbered from 0 through 3.
The array roads contains undirected roads. Each pair [u, v] connects shops u and v.
Return the number of ordered routes that satisfy all of these rules:
- The route contains exactly four distinct shops.
- Consecutive shops are connected by a road.
- The four shop types are exactly
0,1,2, and3, each appearing once.
A route and the same shops visited in reverse order count as two routes. Duplicate road pairs, if supplied, still describe one road.
Function
countShopRoutes(shops: int[], roads: int[][]) → longExamples
Example 1
shops = [0,1,2,3]roads = [[0,1],[1,2],[2,3]]return = 2The valid ordered routes are 0 → 1 → 2 → 3 and 3 → 2 → 1 → 0.
Example 2
shops = [0,1,2,3,3]roads = [[0,1],[1,2],[2,3],[2,4]]return = 4Either type-3 shop can finish the route from 0 through 1 and 2. Each route also counts in reverse, for four ordered routes total.
Example 3
shops = [1,0,3,2,2]roads = [[0,1],[1,2],[1,4],[2,3],[2,4]]return = 6The six valid ordered routes are [0,1,2,3], [0,1,2,4], [0,1,4,2], [3,2,1,0], [4,2,1,0], and [2,4,1,0]. Each visits one shop of every type using the undirected roads.
Constraints
1 <= shops.length <= 200shops[i]is one of0,1,2, or3.0 <= roads.length <= 20000- Every road is
[u, v]with0 <= u, v < shops.lengthandu != v. - The answer fits in a signed
64-bit integer.