Skip to content
Physics and Astronomy
Home Our Teaching Resources C programming PHY3134 connect.html
Back to top

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

  1. Initialise each non-missing node to 'not yet connected'.

  2. 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:

    1. Check if the node is already marked as 'disconnected' and if not return at once (prevents loops).
    2. Mark it as connected.
    3. For each of its (up to four) neighbours, mark it and its neighbours as connected. (i.e. call this function).

Method 2: loop

  1. Initialise each non-missing node to 'not yet connected' and each non-missing node on the top row as connected.

  2. Loop:
    1. 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.

    2. 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'.

                                                                                                                                                                                                                                                                       

Validate   Link-check © Copyright & disclaimer Privacy & cookies Share
Back to top