The enormous family-friendly multinational corporation PB (Pollution Busters) has been hitting headlines this year due to the 2010 Golf of Tigerius oil spill. After an oil rig explosion in April, the company has been in serious hot water.
Due to petroleum toxicity and oxygen depletion, the spill is an environmental catastrophe. It has damaged the local fishing industry, the tourism industry and the habitats of hundreds of wildlife species. PB however, is not particularly worried, as made clear in the CEO's statement that the oil spill is "relatively tiny" in comparison with the "very big ocean".
PB has refused to allow independent scientists to perform accurate measurements on the oil spill rate. The media has been prevented from viewing affected areas or flying over the spill, and threatened with arrest when attempting to investigate.
The international environmentalist organisation Green Peas has employed you to write a program to help them calculate the severity of the environmental impact.
Green Peas has given you a grid of R rows and C columns, representing the environment surrounding the oil rig. The spill originated at the rig, which will be marked on your map with a `$'. Land squares will be marked with a `#' and sea squares will be marked with a `.'. Each day after the initial explosion, every sea square adjacent (north, east, south or west) to either the oil rig or a previously oil-covered sea square becomes covered by oil. Land squares are never covered by oil.
Your program must simulate the spread of the oil spill for K days, then output a map of the surrounding environment with oil-covered sea squares represented by `*'.
To evaluate your solution, the judges will run your program against several different input files. All of these files will adhere to the following bounds:
As some of the test cases will be quite large, you may need to think about how well your solution scales for larger input values. However, not all the cases will be large. Specifically:
Your program should read from the file oilin.txt. The first line of this file will contain three space-separated integers R, C and K. The following R lines will each contain C characters, each of which will be `#' or `.' representing land and sea squares respectively. Exactly one character in the entire grid will be `$', representing the oil rig at sea.
Your program should write to the file oilout.txt. Your output file should consist of R lines, each containing C characters. Each character in this grid should be the same as the corresponding character in the input grid, except for sea squares which have been covered by oil after K days. These should be represented by `*' characters.
4 6 4 ###... .$.... ...### #.#..#
###**. *$**** ***### #*#..#
4 3 2 #.# .$. .## ...
#*# *$* *## ...
The score for each input scenario will be 100% if the correct answer is written to the output file, and 0% otherwise.