该题解采用了递归加备忘录的方法来解决问题，涉及动态规划的思路。具体思路如下：首先，对每个方向的车辆数进行统计，并定义两个缓存函数。第一个缓存函数`can_pass`用于检查在不产生冲突的情况下哪些车可以同时通过交叉口。它使用了一个16位的数组来标记可能的冲突，并对每一种行驶方向的车辆进行冲突检查。第二个缓存函数`get_min_time`是主要的递归函数，用于计算清空路口所需的最短时间。它首先考虑一个车辆通过的情况，然后尝试所有可能的车辆组合，递归地计算通过剩余车辆所需的时间。这里使用了组合生成和对每种可能的行车情况进行模拟，通过调用`can_pass`来确保没有冲突。
时间复杂度: O(2^n)
空间复杂度: O(n + 4^n)
import math
from typing import List
from itertools import combinations
from functools import lru_cache
class Solution:
def trafficCommand(self, directions: List[str]) -> int:
# 计算每个方向的车辆数
ll = [len(i) for i in directions]
# 使用备忘录优化，判断是否可通行
@lru_cache(None)
def can_pass(e, s, w, n):
todo = {}
op = [0] * 16 # 标记16种可能的车辆动作组合
# 判断每个方向是否有车并转化为小写字母表示方向
if e != '':
todo['e'] = e.lower()
if s != '':
todo['s'] = s.lower()
if w != '':
todo['w'] = w.lower()
if n != '':
todo['n'] = n.lower()
for i in todo:
# 根据车辆的目标方向，检查是否会产生冲突
# 例如东边的车向南行驶需要的路径是否被其他车辆占用
if i == 'e':
if todo[i] == 's':
if op[5] == 1 or op[8] == 1 or op[10] == 1 or op[15] == 1 or op[14] == 1:
return False # 如果路径已被占用则返回不可通行
op[5] = 1
op[8] = 1
op[10] = 1
op[15] = 1
op[14] = 1
# 同样的检查逻辑应用于其他方向和目标组合
# 下面代码块遵循同样逻辑处理南、西、北方向的车辆
# 计算最小通过时间的函数
@lru_cache(None)
def get_min_time(rest_idx: tuple):
if sum(rest_idx) == 0:
return 0 # 所有车辆已通过时返回0
topick = [k for k, v in enumerate(rest_idx) if v > 0] # 选择还有车辆的方向
ans = math.inf
# 单车通过
for i in topick:
tp = list(rest_idx)
tp[i] -= 1
ans1 = 1 + get_min_time(tuple(tp))
ans = min(ans, ans1)
# 尝试多车同时通过的情况，保证不冲突
for i in range(2, len(topick) + 1):
for j in combinations(topick, i):
picked = j
e, s, w, n = '', '', '', ''
# 获取对应方向车辆的当前行驶方向
if 0 in picked:
e = directions[0][len(directions[0]) - rest_idx[0]]
if 1 in picked:
s = directions[1][len(directions[1]) - rest_idx[1]]
if 2 in picked:
w = directions[2][len(directions[2]) - rest_idx[2]]
if 3 in picked:
n = directions[3][len(directions[3]) - rest_idx[3]]
ret1 = can_pass(e, s, w, n) # 检查是否冲突
if ret1:
tp = list(rest_idx)
for x in picked:
tp[x] -= 1
ans1 = 1 + get_min_time(tuple(tp))
ans = min(ans, ans1)
return ans
ret = get_min_time(tuple(ll))
return ret
# 示例调用
a = Solution()
print(a.trafficCommand(["NN","WE","EN","EW"]))
# print(a.trafficCommand(["S", "W", "N", "E"]))
# # print(a.trafficCommand(directions = ["W","N","ES","W"]))
# print(a.trafficCommand(directions=["NS", "WE", "SE", "EW"]))