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 counterexplosive 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 counterexplosive 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 counterexplosive device on (a,b) if and only if there is a counterexplosive 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.
Input
 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 counterexplosive device and “.” denotes free cell.
 Input ends with N=0 and M=0. which should not be processed.
Output
 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.
Constraints
 1 ≤ N ≤ 100
 1 ≤ M ≤1000
 Sum of N over all test cases ≤ 2000
Example
Sample Input:
2 1
#.
.#
2 1
##
##
0 0
Sample Output:
Case#1: 1
Case#2: IMPOSSIBLE
Author:  iopc_admin 
Tags  iopc_admin 
Date Added:  2022014 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP 4.3.2, CPP 4.9.2, GO, JAVA 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions