Floodfill
Time limit1sMemory limit1024 MB
Simulate rain falling on a grid where full 8-connected cells share overflow water, then print each cell's water level or report that Atlantis sank.
- Level
Medium4 of 10
- Topics
- Simulation, BFS, Implementation
- Solved
- No attempts yet
Problem
The engineers are now trying to work out how Atlantis sank from information they found in the buildings. The Atlantean scientists knew a flood was coming. They collected rainfall data and divided the continent into a grid of square cells to find which areas would flood and how badly. Each cell can hold a certain amount of water (in helenometers) before it has standing water.
The simulations include the grid of cells with their water retention capacities and the rainfall events. In each rainfall event, X helenometers of rain fall on one cell of the grid. All saturated cells that are adjacent (defined as the 8 cells surrounding a cell) form one large cell for the purpose of distributing water. When a cell fills up, its water is distributed equally to all adjacent unsaturated cells. If any of those cells fill up, the water is distributed equally among the unsaturated cells adjacent to the one large cell it has joined, that is, the cells adjacent to the cell that overflowed into it and the cells adjacent to the cell that just filled up.
The simulation runs for several days, and you output the water saturation level of each cell at the end of the period. All the cells adjacent to a flooded cell are flooded at the same time. The data for each day is in the order the rain fell, so you must fully process each event before moving to the next one, since it never rains in more than one place at once on Atlantis. All cells are empty at the start of each case.
After processing the data for a case, decide whether Atlantis sank. If all cells are filled and the water has nowhere to flow, output "Atlantis Sank". Otherwise, if there was room for the water to flow, output the amount of water in each cell of the grid. If a cell on the edge of the grid fills up, the ocean spaces are ignored, because all of Atlantis is surrounded by a giant levee not built by the US Corp of Engineers, so do not expect it to burst.
The grid is indexed from 0,0 at the top left square. Cells are processed from left to right and from top to bottom. Round all overflow calculations to the nearest 1/100th.
Input
The first line gives the number of cases, . Each case starts with the number of rows and the number of columns, each , followed by the water retention value of every cell in grid order, . Next is the number of days, and then the data for each day in the form of row, column, and amount of rain.