Bomberman and the attack of Emperor Terrorin
All submissions for this problem are available.
The Fiendish Bombers, unleashed by Emporer Terrorin, have invaded Bungeling Empire in Bomber Nebula. You are Dr.Ein, the scientist assisting the Bomberman. Help him to save Planet Bomber!
Consider the Empire as (N+2)x(N+2) maze free of any rocks and obstacles. The Fiendish Bombers have reached the borders of the Empire. They are present on all border cells of the maze except the corners (they don’t like to be cornered :P). Now consider the remaining NxN maze.
Some cells are with counter-explosive devices and so bombs cannot be planted there. The bombs can be planted anywhere on the remaining maze. Because of one of the new invention, the Fire, ability of the Bomberman’s bomb is infinite. That is, if it explodes at (a,b) it will destroy enemies from all the cells on the horizontal line through (a,b) and on the vertical line passing through (a,b). Note that it would not affect any of the counter-explosive devices.
You have an encrypted connection with the Bomberman and can message him (a,b), the coordinates where a bomb can be planted. The cost of each message is M. But the problem is, you forgot to agree upon the directions of the axis while deciding the origin. So, when you message (a,b), Bomberman plants 2 bombs - on (a,b) and on (b,a) (provided they are distinguishable). Also, it is ensured that there is a counter-explosive device on (a,b) if and only if there is a counter-explosive device on (b,a). Your task is to minimize the cost of eliminating all enemies.
Print a single integer, the cost of eliminating all the 4*N enemies. Print IMPOSSIBLE if it is impossible to do so.
- There are several test cases.
- Each test case begins with two integers: N - denoting size of the grid and M - denoting cost of single message.
- N lines follow. Each containing a string of N characters describing the cells of corresponding row. “#” denotes cell with counter-explosive device and “.” denotes free cell.
- Input ends with N=0 and M=0. which should not be processed.
- For each testcase, output a single line, consisting of string "Case#" followed by the case number, a colon and the solution of the corresponding case.
- 1 ≤ N ≤ 100
- 1 ≤ M ≤1000
- Sum of N over all test cases ≤ 2000
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP 4.3.2, CPP 4.9.2, GO, JAVA|
Fetching successful submissions