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
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
Computer Networking: A Top-Down Approach (7th Edition)
7th Edition
ISBN:9780133594140
Author:James Kurose, Keith Ross
Publisher:James Kurose, Keith Ross
Chapter1: Computer Networks And The Internet
Section: Chapter Questions
Problem R1RQ: What is the difference between a host and an end system? List several different types of end...
Related questions
Question
not quite sure how to approach this, i need to do it in c++ and if possible with explanation on each step pls!
Transcribed Image Text: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
2
1
0
2
2
0
1
1
1
2
2
2
1
0
1
2
0
1
2
2
0
2
2
0
2
TIN
1
1
2
2
2
1
0
1
2
0
2
2
2
0
For each solution print out how long it took Trogdor to wreak havoc on the village.
2
2
IN
1
2
0
1
Transcribed Image Text: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
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
This is a popular solution!
Trending now
This is a popular solution!
Step by step
Solved in 5 steps with 4 images
Recommended textbooks for you
Computer Networking: A Top-Down Approach (7th Edi…
Computer Engineering
ISBN:
9780133594140
Author:
James Kurose, Keith Ross
Publisher:
PEARSON
Computer Organization and Design MIPS Edition, Fi…
Computer Engineering
ISBN:
9780124077263
Author:
David A. Patterson, John L. Hennessy
Publisher:
Elsevier Science
Network+ Guide to Networks (MindTap Course List)
Computer Engineering
ISBN:
9781337569330
Author:
Jill West, Tamara Dean, Jean Andrews
Publisher:
Cengage Learning
Computer Networking: A Top-Down Approach (7th Edi…
Computer Engineering
ISBN:
9780133594140
Author:
James Kurose, Keith Ross
Publisher:
PEARSON
Computer Organization and Design MIPS Edition, Fi…
Computer Engineering
ISBN:
9780124077263
Author:
David A. Patterson, John L. Hennessy
Publisher:
Elsevier Science
Network+ Guide to Networks (MindTap Course List)
Computer Engineering
ISBN:
9781337569330
Author:
Jill West, Tamara Dean, Jean Andrews
Publisher:
Cengage Learning
Concepts of Database Management
Computer Engineering
ISBN:
9781337093422
Author:
Joy L. Starks, Philip J. Pratt, Mary Z. Last
Publisher:
Cengage Learning
Prelude to Programming
Computer Engineering
ISBN:
9780133750423
Author:
VENIT, Stewart
Publisher:
Pearson Education
Sc Business Data Communications and Networking, T…
Computer Engineering
ISBN:
9781119368830
Author:
FITZGERALD
Publisher:
WILEY