Challenge 2: Water water everywhere...
NSBCoding :: Coding :: Challenges
Page 1 of 1
Challenge 2: Water water everywhere...
Admin Thu Jun 09, 2011 12:32 pm
Life is good in Trollville. But Alas, the irrigation system is not very good. Currently, it heavily depends on the rainfall throughout the whole region. Good thing is, the cave trolls living in trollville have gotten smarter. At Mt. Troll (the highest mountain in trollville), the citizens have put up a giant magnet on it so that it attracts the rain from the sky. Thus, by allowing the water flow down the mountain, the whole area can have water and can grow more trolltrees. There is a problem however, as Trollville is not flat. In fact, its topography is quite rugged. The cave trolls have separated Trollville into a grid and mapped out the average height of all the squares in the grid. Water can only flow to a square if there is a square with a higher or equal height adjacent to it (adjacent as in a square that is to the North, East, South and West). The mayor of Trollville has employed u (forcibly) to make a program that, given the topography of trollville, calculate the total area covered by water (including Mt. troll and assuming Mt. Troll gives out infinite water and that water does not accumulate in an area).
Input:
Your program must read from a file. The first line of the file will contain an integer W (1 <= W <= 100), which is the width of Trollville. Trollville is a square so it has W x W squares. It is guaranteed that W is odd. Then, foreach square in the grid, there will be an integer H (-100000 <= H <= 100000) which represents the height of that square. The very centre square (i.e. at row (W/2)+1 and column (W/2)+1) is Mt. Troll.
Example:
Input:
5
10 10 10 10 30
10 20 10 40 10
20 10 50 20 10
10 20 10 16 16
10 20 10 14 10
Output:
17
Explanation:
After the flood, it will look something like:
$$ $$ $$ $$ 30
$$ 20 $$ 40 $$
20 $$ $$ $$ $$
10 20 $$ $$ $$
10 20 $$ $$ $$
Notice that the bottom left corner is impenetrable.
Hints:
1. How do you represent the grid?
2. How do you keep track of where it is flooded and where it isn't
Improvements:
Your first solution will probably not be the most optimal, so here's some hints to help you improve it.
1.
Extension:
Here's some stuff that you can do after you have completed the challenge.
1.
Input:
Your program must read from a file. The first line of the file will contain an integer W (1 <= W <= 100), which is the width of Trollville. Trollville is a square so it has W x W squares. It is guaranteed that W is odd. Then, foreach square in the grid, there will be an integer H (-100000 <= H <= 100000) which represents the height of that square. The very centre square (i.e. at row (W/2)+1 and column (W/2)+1) is Mt. Troll.
Example:
Input:
5
10 10 10 10 30
10 20 10 40 10
20 10 50 20 10
10 20 10 16 16
10 20 10 14 10
Output:
17
Explanation:
After the flood, it will look something like:
$$ $$ $$ $$ 30
$$ 20 $$ 40 $$
20 $$ $$ $$ $$
10 20 $$ $$ $$
10 20 $$ $$ $$
Notice that the bottom left corner is impenetrable.
Hints:
1. How do you represent the grid?
2. How do you keep track of where it is flooded and where it isn't
Improvements:
Your first solution will probably not be the most optimal, so here's some hints to help you improve it.
1.
- Spoiler:
- If you stored the flooded squares in the grid, then you'll probably have to go through the entire grid and spread out the water. Is there a better way? Is there an alternative way to store where it is flooded? How do you prevent flooding an area multiple times?
- Spoiler:
- If your program checks for up,down,left and right in separate if statements, then there is an improvement! How do u combine all that into one little block?
Extension:
Here's some stuff that you can do after you have completed the challenge.
1.
- Spoiler:
- Instead of just counting the flooded squares, add to your program so that it prints out a map of the flooded area. Make sure you get your rows and columns in the right way.
- Spoiler:
- Suppose that for every grid that is above a height M has a magnet on it. Modify your program so that it can simulate multiple Mt. trolls.
Admin- Admin
- Posts : 21
Join date : 2011-06-04 -
NSBCoding :: Coding :: Challenges
Page 1 of 1
Permissions in this forum:
You cannot reply to topics in this forum|
|
|