Breadth-first search
CSC263 Tutorial 8
BFS algorithm
BFS(G, s) /* BFS of G star1ng from node s */
colour[1..n] = {white, …, white} d[1..n] = {∞, …, ∞}
P[1..n] = {Nil, Nil, …, Nil} colour[s] = grey
d[s] = 0
Create new queue Q Q.enqueue(s)
while Q is not empty
u = Q.dequeue()
for each node v adjacent to u
if colour[v] = white then colour[v] = grey
d[v] = d[u] + 1
P[v] = u
Q.enqueue(v) colour[u] = black
Suppose we have a graph G = (V,E) containing |V| = n nodes and |E| = m edges.
BFS takes O(n+m) Vme and space.
Example: BFS starVng at node a • All weights iniVally set to infinity.
e
4
a
1 3
d
g
4
i
0
1
b
2
f c
h
4
5
ApplicaVon 1: checking connectedness
e
4
0
a 1
1 3
d
g
4
i
b
2
f c
4
h
• If no node has distance infinity, it’s connected!
• Run BFS on any node
5
ApplicaVon 1: checking connectedness
e
i
d
g
4
0
a 1
1 3
b
2
f c
4
h
• If a node has distance infinity, disconnected!
• Run BFS on any node
5
Distance is infinity!
ApplicaVon 2:
finding connected components
Algorithm:
iniVally label each node 0 c := 1
for each node u = 1..n do
if u is sVll labeled 0 then
do a BFS starVng at u
give the label c to each node reached by the BFS c := c+1
end if end for
ApplicaVon 2:
finding connected components
• IniVally, each node has label 0
d
g
3
i
e
2
a
1 2
1
1
b
2
f c
h
4
4
ApplicaVon 3: finding cycles
• Repeatedly do BFS from any unvisited node, unVl all nodes are visited.
• In any of these BFSs, if we see an edge that points to a gray node, then there is a cycle!
ApplicaVon 3: finding cycles
Enqueue node a
e
f
Dequeue node a
Enqueue node b
Enqueue node d i
Dequeue node b
Try to enqueue a; black, so do nothing
Try to enqueue d; gray node, so cycle!
a
1
d
g
0
1
b
c
Can also use DFS h (next week)
ApplicaVon 4: compuVng distance
• Suppose we have an m x n grid of farms.
• IniVally, one of the farms is on fire!
• At each hour, the fire spreads from each burning farm to each farm (going up, down, leb and right).
• How long before all farms are on fire?
ApplicaVon 4: compuVng distance
• How can we represent this problem as a graph problem?
– Nodes are farms.
– There is an edge between two farms if the farms are adjacent (next to one another).
ApplicaVon 4: compuVng distance
• How should we store this graph in memory? • One possibility (for a 3×3 grid of farms):
Wastes lots of memory!
ApplicaVon 4: compuVng distance • How should we store this graph in memory?
• A more memory efficient way:
– Store any data associated with the farms in a 3×3
array (one element for each farm)
– Two farms are adjacent if their array elements are adjacent in the 3×3 array.
ApplicaVon 4: compuVng distance (for a 15 x 10 grid of farms)
Solu1on: run BFS starVng from the fire to compute the “distance” (actually Vme) to each farm.
ApplicaVon 4: compuVng distance
1
1
1
1
ApplicaVon 4: compuVng distance
2
2
1
2
2
1
1
2
2
1
2
2
ApplicaVon 4: compuVng distance
3
2
3
3
2
1
2
3
3
2
1
1
2
3
3
2
1
2
3
3
2
3
3
ApplicaVon 4: compuVng distance
4
3
2
3
4
4
3
2
1
2
3
4
3
2
1
1
2
3
4
4
3
2
1
2
3
4
4
3
2
3
4
4
3
4
4
ApplicaVon 4: compuVng distance
5
4
3
2
3
4
5
4
3
2
1
2
3
4
5
3
2
1
1
2
3
4
5
4
3
2
1
2
3
4
5
5
4
3
2
3
4
5
5
4
3
4
5
5
4
5
5
ApplicaVon 4: compuVng distance
5
4
3
2
3
4
5
6
4
3
2
1
2
3
4
5
6
3
2
1
1
2
3
4
5
6
4
3
2
1
2
3
4
5
6
5
4
3
2
3
4
5
6
6
5
4
3
4
5
6
6
5
4
5
6
6
5
6
6
ApplicaVon 4: compuVng distance
5
4
3
2
3
4
5
6
7
4
3
2
1
2
3
4
5
6
7
3
2
1
1
2
3
4
5
6
7
4
3
2
1
2
3
4
5
6
7
5
4
3
2
3
4
5
6
7
6
5
4
3
4
5
6
7
7
6
5
4
5
6
7
7
6
5
6
7
7
6
7
7
ApplicaVon 4: compuVng distance
5
4
3
2
3
4
5
6
7
8
4
3
2
1
2
3
4
5
6
7
8
3
2
1
1
2
3
4
5
6
7
8
4
3
2
1
2
3
4
5
6
7
8
5
4
3
2
3
4
5
6
7
8
6
5
4
3
4
5
6
7
8
7
6
5
4
5
6
7
8
8
7
6
5
6
7
8
8
7
6
7
8
8
7
8
ApplicaVon 4: compuVng distance
5
4
3
2
3
4
5
6
7
8
9
4
3
2
1
2
3
4
5
6
7
8
9
3
2
1
1
2
3
4
5
6
7
8
9
4
3
2
1
2
3
4
5
6
7
8
9
5
4
3
2
3
4
5
6
7
8
9
6
5
4
3
4
5
6
7
8
9
7
6
5
4
5
6
7
8
9
8
7
6
5
6
7
8
9
9
8
7
6
7
8
9
9
8
7
8
9
ApplicaVon 4: compuVng distance
5
4
3
2
3
4
5
6
7
8
9
10
4
3
2
1
2
3
4
5
6
7
8
9
10
3
2
1
1
2
3
4
5
6
7
8
9
10
4
3
2
1
2
3
4
5
6
7
8
9
10
5
4
3
2
3
4
5
6
7
8
9
10
6
5
4
3
4
5
6
7
8
9
10
7
6
5
4
5
6
7
8
9
10
8
7
6
5
6
7
8
9
10
9
8
7
6
7
8
9
10
10
9
8
7
8
9
10
ApplicaVon 4: compuVng distance
5
4
3
2
3
4
5
6
7
8
9
10
11
4
3
2
1
2
3
4
5
6
7
8
9
10
11
3
2
1
1
2
3
4
5
6
7
8
9
10
11
4
3
2
1
2
3
4
5
6
7
8
9
10
11
5
4
3
2
3
4
5
6
7
8
9
10
11
6
5
4
3
4
5
6
7
8
9
10
11
7
6
5
4
5
6
7
8
9
10
11
8
7
6
5
6
7
8
9
10
11
9
8
7
6
7
8
9
10
11
10
9
8
7
8
9
10
11
ApplicaVon 4: compuVng distance
5
4
3
2
3
4
5
6
7
8
9
10
11
12
4
3
2
1
2
3
4
5
6
7
8
9
10
11
12
3
2
1
1
2
3
4
5
6
7
8
9
10
11
4
3
2
1
2
3
4
5
6
7
8
9
10
11
12
5
4
3
2
3
4
5
6
7
8
9
10
11
12
6
5
4
3
4
5
6
7
8
9
10
11
12
7
6
5
4
5
6
7
8
9
10
11
12
8
7
6
5
6
7
8
9
10
11
12
9
8
7
6
7
8
9
10
11
12
10
9
8
7
8
9
10
11
12
ApplicaVon 4: compuVng distance
5
4
3
2
3
4
5
6
7
8
9
10
11
12
13
4
3
2
1
2
3
4
5
6
7
8
9
10
11
12
3
2
1
1
2
3
4
5
6
7
8
9
10
11
4
3
2
1
2
3
4
5
6
7
8
9
10
11
12
5
4
3
2
3
4
5
6
7
8
9
10
11
12
13
6
5
4
3
4
5
6
7
8
9
10
11
12
13
7
6
5
4
5
6
7
8
9
10
11
12
13
8
7
6
5
6
7
8
9
10
11
12
13
9
8
7
6
7
8
9
10
11
12
13
10
9
8
7
8
9
10
11
12
13
ApplicaVon 4: compuVng distance
5
4
3
2
3
4
5
6
7
8
9
10
11
12
13
4
3
2
1
2
3
4
5
6
7
8
9
10
11
12
3
2
1
1
2
3
4
5
6
7
8
9
10
11
4
3
2
1
2
3
4
5
6
7
8
9
10
11
12
5
4
3
2
3
4
5
6
7
8
9
10
11
12
13
6
5
4
3
4
5
6
7
8
9
10
11
12
13
14
7
6
5
4
5
6
7
8
9
10
11
12
13
14
8
7
6
5
6
7
8
9
10
11
12
13
14
9
8
7
6
7
8
9
10
11
12
13
14
10
9
8
7
8
9
10
11
12
13
14
ApplicaVon 4: compuVng distance
5
4
3
2
3
4
5
6
7
8
9
10
11
12
13
4
3
2
1
2
3
4
5
6
7
8
9
10
11
12
3
2
1
1
2
3
4
5
6
7
8
9
10
11
4
3
2
1
2
3
4
5
6
7
8
9
10
11
12
5
4
3
2
3
4
5
6
7
8
9
10
11
12
13
6
5
4
3
4
5
6
7
8
9
10
11
12
13
14
7
6
5
4
5
6
7
8
9
10
11
12
13
14
15
8
7
6
5
6
7
8
9
10
11
12
13
14
15
9
8
7
6
7
8
9
10
11
12
13
14
15
10
9
8
7
8
9
10
11
12
13
14
15
ApplicaVon 4: compuVng distance
5
4
3
2
3
4
5
6
7
8
9
10
11
12
13
4
3
2
1
2
3
4
5
6
7
8
9
10
11
12
3
2
1
1
2
3
4
5
6
7
8
9
10
11
4
3
2
1
2
3
4
5
6
7
8
9
10
11
12
5
4
3
2
3
4
5
6
7
8
9
10
11
12
13
6
5
4
3
4
5
6
7
8
9
10
11
12
13
14
7
6
5
4
5
6
7
8
9
10
11
12
13
14
15
8
7
6
5
6
7
8
9
10
11
12
13
14
15
16
9
8
7
6
7
8
9
10
11
12
13
14
15
16
10
9
8
7
8
9
10
11
12
13
14
15
16
ApplicaVon 4: compuVng distance
5
4
3
2
3
4
5
6
7
8
9
10
11
12
13
4
3
2
1
2
3
4
5
6
7
8
9
10
11
12
3
2
1
1
2
3
4
5
6
7
8
9
10
11
4
3
2
1
2
3
4
5
6
7
8
9
10
11
12
5
4
3
2
3
4
5
6
7
8
9
10
11
12
13
6
5
4
3
4
5
6
7
8
9
10
11
12
13
14
7
6
5
4
5
6
7
8
9
10
11
12
13
14
15
8
7
6
5
6
7
8
9
10
11
12
13
14
15
16
9
8
7
6
7
8
9
10
11
12
13
14
15
16
17
10
9
8
7
8
9
10
11
12
13
14
15
16
17
ApplicaVon 4: compuVng distance
5
4
3
2
3
4
5
6
7
8
9
10
11
12
13
4
3
2
1
2
3
4
5
6
7
8
9
10
11
12
3
2
1
1
2
3
4
5
6
7
8
9
10
11
4
3
2
1
2
3
4
5
6
7
8
9
10
11
12
5
4
3
2
3
4
5
6
7
8
9
10
11
12
13
6
5
4
3
4
5
6
7
8
9
10
11
12
13
14
7
6
5
4
5
6
7
8
9
10
11
12
13
14
15
8
7
6
5
6
7
8
9
10
11
12
13
14
15
16
9
8
7
6
7
8
9
10
11
12
13
14
15
16
17
10
9
8
7
8
9
10
11
12
13
14
15
16
17
18
18 hours unVl all farms are on fire!
ApplicaVon 4: modifica1on 1
• What if there are lakes in the grid, where fire cannot pass? Just don’t let BFS visit the lakes!
ApplicaVon 4: modifica1on 1
• What if there are lakes in the grid, where fire cannot pass?
1
1
1
1
ApplicaVon 4: modifica1on 1
• What if there are lakes in the grid, where fire cannot pass?
2
2
1
2
1
1
2
1
2
2
ApplicaVon 4: modifica1on 1
• What if there are lakes in the grid, where fire cannot pass?
3
2
3
2
1
2
1
1
3
2
1
2
3
2
3
ApplicaVon 4: modifica1on 1
• What if there are lakes in the grid, where fire cannot pass?
3
2
3
4
2
1
2
1
1
3
2
1
2
4
3
2
3
4
ApplicaVon 4: modifica1on 1
• What if there are lakes in the grid, where fire cannot pass?
3
2
3
4
5
2
1
2
1
1
3
2
1
2
5
4
3
2
3
4
5
5
ApplicaVon 4: modifica1on 1
• What if there are lakes in the grid, where fire cannot pass?
3
2
3
4
5
6
2
1
2
6
1
1
3
2
1
2
6
5
4
3
2
3
4
5
6
6
5
6
6
ApplicaVon 4: modifica1on 1
• What if there are lakes in the grid, where fire cannot pass?
3
2
3
4
5
6
7
2
1
2
6
7
1
1
3
2
1
2
6
7
5
4
3
2
3
4
5
6
7
6
5
6
7
7
6
7
7
ApplicaVon 4: modifica1on 1
• What if there are lakes in the grid, where fire cannot pass?
3
2
3
4
5
6
7
8
2
1
2
6
7
8
1
1
8
3
2
1
2
6
7
8
5
4
3
2
3
4
5
6
7
8
6
5
6
7
8
7
6
7
8
8
7
8
8
8
ApplicaVon 4: modifica1on 1
• What if there are lakes in the grid, where fire cannot pass?
3
2
3
4
5
6
7
8
9
2
1
2
6
7
8
9
1
1
8
9
3
2
1
2
6
7
8
9
5
4
3
2
3
4
5
6
7
8
6
5
6
7
8
9
7
6
7
8
9
8
7
8
9
8
9
9
8
9
9
9
ApplicaVon 4: modifica1on 1
• What if there are lakes in the grid, where fire cannot pass?
3
2
3
4
5
6
7
8
9
10
2
1
2
6
7
8
9
10
1
1
8
9
10
3
2
1
2
6
7
8
9
5
4
3
2
3
4
5
6
7
8
6
5
6
7
8
9
7
6
7
8
9
8
7
8
9
8
9
9
8
9
10
10
9
10
10
9
10
10
ApplicaVon 4: modifica1on 1
• What if there are lakes in the grid, where fire cannot pass?
3
2
3
4
5
6
7
8
9
10
11
2
1
2
6
7
8
9
10
11
1
1
8
9
10
3
2
1
2
6
7
8
9
5
4
3
2
3
4
5
6
7
8
6
5
6
7
8
9
7
6
7
8
9
8
7
8
9
8
9
9
8
9
10
11
10
9
10
11
10
9
10
11
11
10
11
ApplicaVon 4: modifica1on 1
• What if there are lakes in the grid, where fire cannot pass?
3
2
3
4
5
6
7
8
9
10
11
12
2
1
2
6
7
8
9
10
11
12
1
1
8
9
10
3
2
1
2
6
7
8
9
5
4
3
2
3
4
5
6
7
8
6
5
6
7
8
9
7
6
7
8
9
8
7
8
9
8
9
9
8
9
10
11
10
9
10
11
12
10
9
10
11
12
11
10
11
12
ApplicaVon 4: modifica1on 1
• What if there are lakes in the grid, where fire cannot pass?
3
2
3
4
5
6
7
8
9
10
11
12
2
1
2
6
7
8
9
10
11
12
13
1
1
8
9
10
3
2
1
2
6
7
8
9
5
4
3
2
3
4
5
6
7
8
6
5
6
7
8
9
7
6
7
8
9
8
7
8
9
8
9
9
8
9
10
11
10
9
10
11
12
13
10
9
10
11
12
11
10
11
12
13
ApplicaVon 4: modifica1on 1
• What if there are lakes in the grid, where fire cannot pass?
3
2
3
4
5
6
7
8
9
10
11
12
2
1
2
6
7
8
9
10
11
12
13
14
1
1
8
9
10
14
3
2
1
2
6
7
8
9
5
4
3
2
3
4
5
6
7
8
6
5
6
7
8
9
7
6
7
8
9
8
7
8
9
8
9
14
9
8
9
10
11
10
9
10
11
12
13
14
10
9
10
11
12
11
10
11
12
13
14
ApplicaVon 4: modifica1on 1
• What if there are lakes in the grid, where fire cannot pass?
3
2
3
4
5
6
7
8
9
10
11
12
2
1
2
6
7
8
9
10
11
12
13
14
1
1
8
9
10
14
15
3
2
1
2
6
7
8
9
15
5
4
3
2
3
4
5
6
7
8
6
5
6
7
8
9
7
6
7
8
9
8
7
8
9
8
9
14
15
9
8
9
10
11
10
9
10
11
12
13
14
15
10
9
10
11
12
11
10
11
12
13
14
15
ApplicaVon 4: modifica1on 1
• What if there are lakes in the grid, where fire cannot pass?
3
2
3
4
5
6
7
8
9
10
11
12
2
1
2
6
7
8
9
10
11
12
13
14
1
1
8
9
10
14
15
3
2
1
2
6
7
8
9
16
15
16
5
4
3
2
3
4
5
6
7
8
16
6
5
6
7
8
9
7
6
7
8
9
16
8
7
8
9
8
9
14
15
16
9
8
9
10
11
10
9
10
11
12
13
14
15
10
9
10
11
12
11
10
11
12
13
14
15
ApplicaVon 4: modifica1on 1
• What if there are lakes in the grid, where fire cannot pass?
3
2
3
4
5
6
7
8
9
10
11
12
2
1
2
6
7
8
9
10
11
12
13
14
1
1
8
9
10
14
15
3
2
1
2
6
7
8
9
16
15
16
5
4
3
2
3
4
5
6
7
8
17
16
17
6
5
6
7
8
9
17
7
6
7
8
9
16
17
8
7
8
9
8
9
14
15
16
17
9
8
9
10
11
10
9
10
11
12
13
14
15
10
9
10
11
12
11
10
11
12
13
14
15
ApplicaVon 4: modifica1on 1
• What if there are lakes in the grid, where fire cannot pass?
3
2
3
4
5
6
7
8
9
10
11
12
2
1
2
6
7
8
9
10
11
12
13
14
1
1
8
9
10
14
15
3
2
1
2
6
7
8
9
16
15
16
5
4
3
2
3
4
5
6
7
8
17
16
17
6
5
6
7
8
9
18
17
18
7
6
7
8
9
16
17
18
8
7
8
9
8
9
14
15
16
17
18
9
8
9
10
11
10
9
10
11
12
13
14
15
10
9
10
11
12
11
10
11
12
13
14
15
ApplicaVon 4: modifica1on 1
• What if there are lakes in the grid, where fire cannot pass?
5
6
7
8
9
10
3
4
5
6
7
8
9
3
2
1
2
3
8
9
10
2
1
1
2
10
11
3
2
1
2
3
11
12
4
4
9
10
11
5
6
6
5
6
7
8
9
10
6
7
8
7
6
7
8
9
10
11
7
8
9
8
7
8
9
11
12
8
9
10
9
8
9
12
13
9
10
14
13
14
10
11
16
15
14
15
11
12
16
17
18
17
16
15
12
13
14
15
16
17
18
17
14
15
16
17
18
19
18
19 hours unVl all farms are on fire!
ApplicaVon 4: modifica1on 1 • Will the fire always burn everything?
ApplicaVon 4: modifica1on 1 • Will the fire always burn everything?
1
1
1
1
ApplicaVon 4: modifica1on 1 • Will the fire always burn everything?
2
1
2
1
1
2
1
2
2
ApplicaVon 4: modifica1on 1 • Will the fire always burn everything?
2
1
2
1
1
3
2
1
2
3
2
3
ApplicaVon 4: modifica1on 1 • Will the fire always burn everything?
2
1
2
1
1
3
2
1
2
4
3
2
3
4
ApplicaVon 4: modifica1on 1 • Will the fire always burn everything?
2
1
2
1
1
3
2
1
2
5
4
3
2
3
4
5
ApplicaVon 4: modifica1on 1 • Will the fire always burn everything?
2
1
2
1
1
3
2
1
2
5
4
3
2
3
4
6
5
6
ApplicaVon 4: modifica1on 1 • Will the fire always burn everything?
2
1
2
1
1
3
2
1
2
5
4
3
2
3
4
6
5
7
6
ApplicaVon 4: modifica1on 1 • Will the fire always burn everything?
∞
∞
∞
∞
∞
∞
∞
∞
∞
2
1
2
∞
∞
∞
∞
∞
∞
∞
∞
∞
1
1
∞
∞
∞
∞
∞
3
2
1
2
∞
∞
∞
∞
∞
∞
∞
5
4
3
2
3
4
∞
∞
∞
∞
∞
∞
6
5
∞
∞
∞
∞
∞
∞
∞
7
6
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
All of these farms are safe!
ApplicaVon 4: modifica1on 2
• What if mulVple fires start at the same Vme? • Just place all fires in the iniVal BFS queue!
ApplicaVon 4: modifica1on 2
• What if mulVple fires start at the same Vme? • Just place all fires in the iniVal BFS queue!
1
1
1
1
1
1
1
1
1
1
1
1
ApplicaVon 4: modifica1on 2
• What if mulVple fires start at the same Vme? • Just place all fires in the iniVal BFS queue!
2
1
2
2
1
2
2
1
1
2
1
1
2
1
2
2
1
2
2
2
1
2
2
1
1
2
2
1
2
ApplicaVon 4: modifica1on 2
• What if mulVple fires start at the same Vme? • Just place all fires in the iniVal BFS queue!
3
2
1
2
3
2
1
2
2
1
1
2
3
1
1
2
1
2
3
2
1
2
3
2
3
3
2
3
3
3
1
2
3
3
2
1
1
2
3
3
2
1
2
3
ApplicaVon 4: modifica1on 2
• What if mulVple fires start at the same Vme? • Just place all fires in the iniVal BFS queue!
4
3
2
1
2
3
4
2
1
2
2
1
1
2
3
4
1
1
2
1
2
3
2
1
2
4
3
2
3
4
3
2
3
4
4
3
4
4
4
3
4
4
1
2
3
4
3
2
1
1
2
3
4
4
3
2
1
2
3
4
ApplicaVon 4: modifica1on 2
• What if mulVple fires start at the same Vme? • Just place all fires in the iniVal BFS queue!
4
3
2
1
2
3
4
5
2
1
2
2
1
1
2
3
4
5
1
1
2
1
2
3
2
1
2
4
3
2
3
5
4
3
2
3
4
4
3
4
5
4
5
4
5
3
4
5
4
1
2
3
5
4
3
2
1
1
2
3
4
5
5
4
3
2
1
2
3
4
5
ApplicaVon 4: modifica1on 2
• What if mulVple fires start at the same Vme? • Just place all fires in the iniVal BFS queue!
4
3
2
1
2
3
4
5
6
2
1
2
2
1
1
2
3
4
5
6
1
1
2
1
2
6
3
2
1
2
4
3
2
3
5
4
3
2
3
4
4
3
4
6
5
4
5
4
5
6
3
4
5
4
1
2
3
6
5
4
3
2
1
1
2
3
4
5
6
6
5
4
3
2
1
2
3
4
5
6
ApplicaVon 4: modifica1on 2
• What if mulVple fires start at the same Vme? • Just place all fires in the iniVal BFS queue!
4
3
2
1
2
3
4
5
6
2
1
2
2
1
1
2
3
4
5
6
1
1
2
1
2
6
7
3
2
1
2
4
3
2
3
7
5
4
3
2
3
4
4
3
4
6
5
4
5
4
5
7
6
3
4
5
4
1
2
3
6
7
5
4
3
2
1
1
2
3
4
5
6
7
6
5
4
3
2
1
2
3
4
5
6
7
ApplicaVon 4: modifica1on 2
• What if mulVple fires start at the same Vme? • Just place all fires in the iniVal BFS queue!
4
3
2
1
2
3
4
5
6
2
1
2
2
1
1
2
3
4
5
6
1
1
2
1
2
6
7
3
2
1
2
4
3
2
3
8
7
8
5
4
3
2
3
4
4
3
4
8
6
5
4
5
4
5
7
6
3
4
5
8
4
1
2
3
6
7
8
5
4
3
2
1
1
2
3
4
5
6
7
6
5
4
3
2
1
2
3
4
5
6
7
ApplicaVon 4: modifica1on 2
• What if mulVple fires start at the same Vme? • Just place all fires in the iniVal BFS queue!
4
3
2
1
2
3
4
5
6
2
1
2
2
1
1
2
3
4
5
6
1
1
2
1
2
6
7
3
2
1
2
4
3
2
3
8
7
8
5
4
3
2
3
4
4
3
4
9
8
9
6
5
4
5
4
5
9
7
6
3
4
5
8
9
4
1
2
3
6
7
8
9
5
4
3
2
1
1
2
3
4
5
6
7
6
5
4
3
2
1
2
3
4
5
6
7
ApplicaVon 4: modifica1on 2
• What if mulVple fires start at the same Vme? • Just place all fires in the iniVal BFS queue!
4
3
2
1
2
3
4
5
6
2
1
2
2
1
1
2
3
4
5
6
1
1
2
1
2
6
7
3
2
1
2
4
3
2
3
8
7
8
5
4
3
2
3
4
4
3
4
9
8
9
6
5
4
5
4
5
10
9
10
7
6
3
4
5
8
9
10
4
1
2
3
6
7
8
9
10
5
4
3
2
1
1
2
3
4
5
6
7
6
5
4
3
2
1
2
3
4
5
6
7
ApplicaVon 4: modifica1on 2
• What if mulVple fires start at the same Vme? • Just place all fires in the iniVal BFS queue!
5
6
7
5
6
3
4
5
6
4
5
2
1
2
3
4
3
4
1
1
2
2
3
2
1
2
3
1
2
4
4
1
1
3
2
4
4
3
2
1
2
2
1
2
3
4
5
4
3
2
3
1
1
2
3
4
5
3
4
2
1
2
3
4
5
4
5
3
2
6
5
6
4
3
8
7
6
7
5
4
8
9
10
9
8
7
6
5
6
7
8
9
10
9
6
7
8
9
10
11
10
11 hours unVl all farms are on fire!
ApplicaVon 4:
other modifica1ons to think about
• What if fires start at different Vmes?
• What if fires spread at different speeds?
A neat problem to think about
• It’s the year 2241. You’re in a cave and it’s collapsing! A device tells you when each secVon of ceiling will cave in. Can you escape?
19
16
14
12
16
13
20
21
19
27
24
20
20
10
9
18
20
17
16
17
18
23
18
16
9
12
14
14
20
19
20
16
13
7
7
9
11
16
24
20
6
7
12
14
20
5
8
12
9
25
22
15
5
6
14
9
14
10
25
23
21
1
1
15
16
11
19
26
19
25
2
12
18
24
24
13
27
30
7
8
13
17
17
13
19
22
20
21
23
20
12
10
12
15
18
16
15
20
18
16
19
18
15
A neat problem to think about
• It’s the year 2241. You’re in a cave and it’s collapsing! A device tells you when each
secVon of ceiling will cave in. Can you escape?
Here’s a sample solu1on. How
would you solve it in general?
5
1
7
10
6
1
8
12
27
23
13
15
24
18
17
18
20
16
17
16
19
13
15
16
20
14
15
19
20
14
10
9
16
22
18
12
7
14
11
20
16
16
18
10
21
19
13
20
23
18
20
17
19
13
20
15
21
16
25
26
27
12
19
17
23
19
18
6
19
7
20
16
12
13
14
20
7
5
9
7
8
12
9
12
14
11
9
16
25
14
24
22
20
20
15
21
25
2
12
18
24
24
30