from collections import deque
# Lecture d'une suite de cas à tester.
# Aucun contrôle n'est fait sur la validité
# syntaxique de ce qui est lu dans le fichier
def readProblem(filename):
problemList = []
with open(filename) as f:
nCases = int(f.readline().split()[0])
f.readline()
for i in range(nCases):
start = tuple(int(x) for x in f.readline().split())
dest = tuple(int(x) for x in f.readline().split())
forbiddenSets = set()
nbForbidden = int(f.readline().split()[0])
for j in range(nbForbidden):
forbiddenSets.add(tuple(int(x) for x in f.readline().split()))
f.readline()
problemList.append((start, dest, forbiddenSets))
return problemList
def bfs(graph, start=0):
to_visit = deque()
dist = {node: float('inf') for node in graph}
dist[start] = 0
to_visit.appendleft(start)
while to_visit > 0: # une file vide évalue à Faux
node = to_visit.pop()
for neighbor in graph[node]:
if dist[neighbor] == float('inf'):
dist[neighbor] = dist[node] + 1
#prec[neighbor] = node
to_visit.appendleft(neighbor)
return dist#, prec
# https://jill-jenn.net/tp/cs/
def create_graph(f):
graph = {}
for a in range(10):
for b in range(10):
for c in range(10):
for d in range(10):
graph[(a, b, c, d)] = set()
for da, db, dc, dd in [(1, 0, 0, 0), (-1, 0, 0, 0),
(0, 1, 0, 0), (0, -1, 0, 0),
(0, 0, 1, 0), (0, 0, -1, 0),
(0, 0, 0, 1), (0, 0, 0, -1)]:
graph[(a, b, c, d)].add(((a + da) % 10, (b + db) % 10,
(c + dc) % 10, (d + dd) % 10))
graph[(a, b, c, d)] -= f
return graph
def BFS(start, dest, f):
graph = create_graph(f)
dist = bfs(graph, start)
return dist[dest]
if __name__ == '__main__':
problems = readProblem('roues-codeuses-exemple.txt')
for start, dest, f in problems:
print(BFS(start, dest, f))
