Expert · Graphs · 229 of 264
Spreading mould
Each minute, mould (M) spreads to the fresh fruit (F) next to it (up, down, left, right). Empty spots are dots. After how many minutes is all fruit mouldy? Print -1 if some fruit never gets mould.
Input: r and c, then r lines. Output: the number of minutes.
Examples
Input
3 3 MFF FF. .FF
Output
4
Input
3 3 MFF .FF F.F
Output
-1
Input
1 2 .M
Output
0
One more test checks other inputs when you press Check.
Stuck? The idea behind graphs
A graph is places (nodes) joined by edges. Keep it as a dictionary of neighbours: graph[a] is the list of nodes next to a.
Breadth-first search, with a queue, finds the shortest path when every step costs the same; Dijkstra's algorithm, with a heap, when steps cost different amounts.
from collections import deque
graph = {1: [2, 3], 2: [4], 3: [4], 4: []}
dist = {1: 0}
queue = deque([1])
while queue:
node = queue.popleft()
for nxt in graph[node]:
if nxt not in dist:
dist[nxt] = dist[node] + 1
queue.append(nxt)
print(dist[4])Watch for: Mark a node as seen when you add it to the queue, not when you take it out, or it is added many times.