AMR11J  Goblin Wars
The wizards and witches of Hogwarts School of Witchcraft found Prof. Binn's History of Magic lesson to be no less boring than you found your own history classes. Recently Binns has been droning on about Goblin wars, and which goblin civilization fought which group of centaurs where etc etc. The students of Hogwarts decided to use the newfangled computer to figure out the outcome of all these wars instead of memorizing the results for their upcoming exams. Can you help them?
The magical world looks like a 2D R*C grid. Initially there are many civilizations, each civilization occupying exactly one cell. A civilization is denoted by a lowercase letter in the grid. There are also certain cells that are uninhabitable (swamps, mountains, sinkholes etc.)  these cells are denoted by a '#' in the grid. All the other cells  to which the civilizations can move  are represented by a '.' in the grid.
A cell is said to be adjacent to another cell if they share the same edge  in other words, for a cell (x,y), cells (x1, y), (x, y1), (x+1, y), (x, y+1) are adjacent, provided they are within the boundaries of the grid. Every year each civilization will expand to all unoccupied adjacent cells. If it is already inhabited by some other civilization, it just leaves the cell alone. It is possible that two or more civilizations may move into an unoccupied cell at the same time  this will lead to a battle between the civilizations and the cell will be marked with a '*'. Note that the civilizations fighting in a particular cell do not try to expand from that cell, but will continue to expand from other cells, if possible.
Given the initial grid, output the final state of the grid after no further expansion by any civilization is possible.
Input (STDIN):
The first line contains T, the number of cases. This is followed by T test case blocks.
Each test case contains two integers, R, C.
This is followed by R lines containing a string of length C. The jth letter in the ith row describes the state of the cell in year 0.
Each cell is either a
1. '.' which represents an unoccupied cell
2. '#' which represents a cell that cannot be occupied
3. A civilization represented by a lowercase letter ('a'  'z')
Output (STDOUT):
For each test case, print the final grid after no expansion is possible. Apart from the notations used in the input, use '*' to denote that a battle is being waged in that particular cell.
Print a blank line at the end of each case.
Constraints:
1 <= R, C <= 500
1 <= T <= 5
Sample Input:
5
3 5
#####
a...b
#####
3 4
####
a..b
####
3 3
#c#
a.b
#d#
3 3
#c#
...
a.b
3 5
.....
.#.#.
a...b
Sample Output:
#####
aa*bb
#####
####
aabb
####
#c#
a*b
#d#
#c#
acb
a*b
aa*bb
a#.#b
aa*bb
hide comments
nadstratosfer:
20190622 06:16:40
Unreasonable TL prevents AC in Python. Input is clean, no whitespaces in grid layout except one linebreak per row.


kshubham02:
20160609 13:33:27
What should the output of this test case be?


Manoj Kumar Regar:
20160221 10:14:04
Civilizations are differentiated only be lowercase letters. If same community tries to take a cell from more than one side, then no need for '*'. 

dunnohyet:
20140926 10:16:16
finally accepted!! :D 

Mr.Stark:
20140829 06:53:40
My 50th AC 

Siddharth Shah:
20131018 15:21:20
i'm getting WA. Any boundary case pls?? 

Jignesh:
20130801 09:37:42
nice problem :)


Aditya Gourav:
20130326 10:54:17
yay, got ac in first attempt :D 

guy fawkes:
20130317 12:52:14
wtf!! tle again!!!!! can v use stl?? Last edit: 20130319 14:12:21 

J.A.R.V.I.S.:
20121223 08:55:59
nice one :) 
Added by:  Varun Jalan 
Date:  20111215 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Varun/Venkatesh/Pratik  ICPC Asia regionals, Amritapuri 2011 