Working out which nodes are connected to the top edge
Background
We have three possible states for a node:
- Missing.
- Connected to the top row.
- Not (yet) connected to the top row.
We now want to mark the nodes as connected.
Remember: in what follows, don't forget to deal
with the edge problem.
Method 1: recursion
- Initialise each non-missing node to 'not yet connected'.
- Go along the top row connecting each node and its neighbours.
You will need to write a function to connect a node and its neighbours
which will:
- Check if the node is already marked as 'disconnected' and if not return
at once (prevents loops).
- Mark it as connected.
- For each of its (up to four) neighbours, mark it
and its neighbours as connected. (i.e. call this function).
Method 2: loop
- Initialise each non-missing node to 'not yet connected'
and each non-missing node on the top row as connected.
- Loop:
- Sweep through every node, other than on the top row,
and mark it as "connected" if any of its four neighbours is connected
and it itself is disconnected.
- If the step above did not connect any new nodes exit the loop, otherwise
go back to step one.
After you have connected them
Write a function to go along the bottom row and see
if any is connected, if one is return '1', otherwise return '0'.