Step $1$: Create a Node

A node represents the x and y position of a pixel and it's neighbours.

class Node:

def $\_\_$init$\_\_($self$,$ x$,$ y$)$:

self.x $=$ x

self.y $=$ y

self.neighbours $=$ list$()$

Step $2$: Create an Image

The image with $0$ and $1$ data, the $0$ represents the black pixels and the $1$ represents the white pixels.

image $=[$

$[1,0,0,0,0,1,1],$

$[1,1,0,1,0,1,0],$

$[0,1,1,1,0,1,0],$

$[0,1,1,1,1,1,0],$

$[0,1,1,0,1,0,0],$

$[0,1,1,0,1,0,0],$

$[0,1,1,1,1,1,1],$

$]$

$$

$$

Step $3$: Implement the flood fill algorithm

Write the flood fill algorithm using breadth first search.

The flood fill algorithm is an algorithm used determine the area connected to a given point in an image that has a similar color. It starts from a specified seed point and floods outwards.

Variables of interest:

The explored variable is a set, meaning that only unique values can be inserted into the data structure.

The queue variable is a list, but treated as a queue, meaning that the element removed from the queue was the first element added.

class Graph:

explored $=$ set$()$

$$

def floodFill$($self$,$ image, x$,$ y$,$ pixel$)$:

start $=$ Node$($x$,$ y$)$

$$

queue $=$ list$()$

$$

queue.append$($start$)$

$$

# Remember to add the x and y coordinates of newly discovered nodes to the explored set

$$

###

### YOUR CODE HERE

###

$$

# Return the modified image represented as a $2$D array of numbers

$$

return image

$$

def neighbours$($self$,$ image, x$,$ y$,$ currentNode$)$:

U $=$ y $-1$

D $=$ y $+1$

L $=$ x $-1$

R $=$ x $+1$

# An edge is valid if the pixel is newly discovered, i$.$e$.$ an edge is created when the neighbour's pixel value is one.

$$

# Write the neighbours function to find the neighbours in four directions for a given pixel.

$$

# Append a valid Node to the neighbours of the currentNode

$$

# Remember to do boundary checking

$$

###

### YOUR CODE HERE

###

# Return the current node's $($the pixel in question$)$ neighbours, not always a maximum of four.

$$

return currentNode.neighbours

Step $4$: Definition of the start function

Drives the graph and executes the flood fill algorithm.

def start$()$:

$$

# Sample image represented as $2$D array of numbers

$$

graph $=$ Graph$()$

$$

print$($graph$.$floodFill$($image$,2,2,2))$

# DO NOT REMOVE THE RETURN STATEMENT!

$$

return graph

Step $5$: Call the start function

By calling the start function, the function returns the graph and its properties.

This is useful to debug your algorithm.

graph $=$ start$()$

###

### AUTOGRADER TEST $-$ DO NOT REMOVE

###

$$

###

### AUTOGRADER TEST $-$ DO NOT REMOVE

###

$$

###

### AUTOGRADER TEST $-$ DO NOT REMOVE

###