Algorithms and Data Structures for Programming Contests

Graph Traversal Algorithms (Cont'd)

Regroup (1)

High-level solution?

1. Read input into a 2D array.
2. Scan input to generate graph representation of connections:
   1. For each number, "flood-fill" to find all portal entrances and store in a list.
   2. For each portal exit, "flood-fill" to find all numbers and portal entrances and store in a list.
   Result is adjacency list representation of graph: list of neighbours for every node.
   Adjacency lists for sample input:
   • 1: [a, e]
   • 2: [f]
   • 3: [c]
   • 4: []
   • 5: [b]
   • a: [2, f]
   • b: [3, c]
   • c: [4]
   • d: [d]
   • e: [3, c]
   • f: [1, a, e]
3. Perform BFS/DFS on graph to generate lists of reachable points of interest — but modified so that points of interest cannot be used as intermediary nodes.
4. Print sorted lists, in order.

What's "flood-fill"?

• Recursive algorithm to find all points reachable from a position.
• Initialize a separate array visited with the same dimensions as the floor plan, with values False everywhere. Then, call flood_fill(position).

    flood_fill(start):
        visited[start] = True
        if left(start) is not a wall and is not visited:
            flood_fill(left(start))
        if up(start) is not a wall and is not visited:
            flood_fill(up(start))
        if right(start) is not a wall and is not visited:
            flood_fill(right(start))
        if down(start) is not a wall and is not visited:
            flood_fill(down(start))

• (Really, this is just another DFS!)

Try it! (2)

• Try Problem J5 (Knight Hop) from the CCC programming contest.
• Ignore issues of input/output for now: suppose you already have the data stored in an appropriate data structure of your choice.

Regroup

© Copyright 2012–2015 François Pitt <francois.pitt@utoronto.ca>
last updated at 08:25 (EST) on Thu 5 Mar 2015
Algorithms and Data Structures by François Pitt is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.