not quite sure how to approach this, i need to do it in c++ and if possible with explanation on each step pls!

While playing Trogdor the board game with friends recently (a fantastic cooperative game where you take turn controlling a dragon and you burn the land, the peasants, and even some thatched roof cottages) the inspiration for this fun little homework problem came up. You are given an NXM grid with the following potential board states A space will be either empty (represented with a 0, that is to say no cottage is present) A space will contain a thatched roof cottage (represented with a 1) A space will contain a thatched roof cottage on fire (represented with a 2) We have an ambiguous unit of time, but each unit of time a cottage on fire will spread the flames to any cottage adjacent North, South, East or West (ignore diagonal adjacency for this problem). You will create two solutions to this problem (and use the timer class to time them). The first solution will be an iterative brute force solution where you will make a new 2D array with the results of the first board and continuously update it until the state no longer changes, that is to say all houses are either on fire or all houses that could be on fire are on fire and the houses that could not burn are still standing. Time this solution using the timer class you used on HW1. The second solution will be an intelligent solution using a Breadth First Search Start a BFS at each burning cottage (push that coordinate into your queue) Keep track of the visited coordinates, each burning cottage will catch an adjacent not burning cottage on fire (North, South, East or West). For each BFS, each time unit can be stored and the maximum amount will be how many time units it takes to ignite all cottages (assuming they can). That will be your total time units Trogdor takes to show no mercy towards the village. Determine how many units of time it takes for every cottage to burn and print that out to the console, "Trogdor destroyed the village in T time units". If any cottages remain instead print out that cottages remain (Trogdor did not destroy the village) "Trogdor did not destroy T cottages". In the example below the burning house starts at the top left. Notice it takes 4 iterations to catch the remaining cottages on fire. Therefore you would return For each solution print out how long it took Trogdor to wreak havoc on the village