Make a Voronoi diagram (ASCII variant) Suppose you're given some distinct uppercase letters scattered in a rectangular array of otherwise-blank cells. Each cell in the array belongs to the letter nearest to it, defined as the letter reachable in the smallest number of horizontal and/or vertical steps -- no diagonal steps. (If a cell is equidistant from two or more nearest letters, it belongs to whichever of those letters is first in alphabetical order. A cell with an uppercase letter in it belongs to that letter.) Boundary-cells are those that are horizontally or vertically adjacent to one or more cells that do not belong to the letter that they themselves belong to.

Write a procedure subprogram with the following behavior, producing a kind of Voronoi diagram ...

Input: Any ASCII string composed only of dots, uppercase letters, and newlines, such that when printed it displays a rectangular array of the kind described above, with dots acting as blanks.

Output: A printout of the input string with each blank boundary-cell replaced by the lowercase version of the letter it belongs to. (The subprogram does the printing.)

Example 1

Input:

......B..
.........
...A.....
.........
.......D.
.........
.C.......
.....E...
.........


Output:

...ab.B..
....ab.bb
...A.abdd
aa...ad..
cca.ad.D.
..caeed..
.C.ce.edd
..ce.E.ee
..ce.....


A sketch highlighting the boundaries:

 


Example 2

Input:

............................U...........
......T.................................
........................................
.....................G..................
..R.......S..........F.D.E............I.
.........................H..............
.....YW.Z...............................
......X.................................
........................................
........................................
......MN...........V....................
......PQ................................
........................................
.............L...............J..........
........................................
........................................
....C...........K.......................
........................................
..................................A.....
...........B............................


Output:

..rt.....ts...sg......gduu..U.....ui....
..rt..T..ts...sg......gddeu......ui.....
...rt...ts....sg......gddeeu....ui......
....rttts.....sggggggGgdde.euuuui.......
..R.rywss.S....sfffffFdDdEeeeeeei.....I.
...ryywwzs.....sf....fddhHhhhhhhhi......
..ryyYWwZzs..sssffff.fddh.......hi......
..rxxxXxzzs.sllvvvvvffddh....hhhhi......
rrrxxxxnzzssl.lv....vfddh...hjjjjii.....
mmmmmmmnnnnnl.lv.....vvdh..hj....jai....
mmmmmmMNnnnnl.lv...V...vvhhj.....jaai...
ppppppPQqqql...lv.......vhj......ja.ai..
ppppp.pq.ql....lkv.....vjj.......ja..aii
cccccppqql...L.lkkv...vj.....J...ja...aa
.....cpqqlll..lk..kvvvvj........ja......
......cccbbbllk....kkkkj.......ja.......
....C...cb..bk..K......kj.....ja........
.......cb....bk........kjjjjjja.........
......cb......bk.......kaaaaaa....A.....
.....cb....B...bk......ka...............


Color enhancement:
Python 3 - 424 422 417 332 295 characters:
def v(s):
 w=s.find(&quot;\n&quot;)+1;n=(-1,1,-w,w);r=range(len(s));x=str.replace;s=x(x(s,*&quot;.~&quot;),*&quot;\n~&quot;)+&quot;~&quot;*w;t=0
 while s!=t:t=s;s=[min(s[i+j]for j in n).lower()if&quot;~&quot;==s[i]and(i+1)%w else s[i]for i in r]+[&quot;~&quot;]*w
 print(x(&quot;&quot;.join(s[i]if any(s[i]!=s[i+j].lower()!=&quot;~&quot;for j in n)else&quot;.&quot;for i in r),*&quot;~\n&quot;))

There are three parts, each of which needs to be on its own line due to Python's syntax:

The first line sets up the variables. w is the width of a row of the board (including the newline at the end, which will be recycled as a padding column). r is a range object that indexes all the characters in s. n is a tuple of index offsets to get at the neighbors of a character (so if you wanted to allow the letters to spread out diagonally, you'd just need to add -w-1,-w+1,w-1,w+1 to the tuple). x is a short name for the str.replace method, which gets used several times in the later code (the calls will look odd though, since I use x(s,*&quot;xy&quot;) to save characters, rather than the conventional s.replace(&quot;x&quot;, &quot;y&quot;)). The s parameter string is modified slightly at this point as well, with its . characters and newlines being replaced by ~ characters (because they sort after all letters). A row's worth of padding ~ characters are also added to the end. t will later be used as a reference to the &quot;old&quot; version of s, but it needs to be initialized to something not equal to s at the start, and zero takes only one character (a more Pythonic value would be None, but that's three extra characters).
The second line has a loop that repeatedly updates s using a list comprehension. As the comprehension iterates over the indexes of s, ~ characters are replaced by the min of their neighbors. If a ~ character was completely surrounded by other ~s, this will do nothing. If it was next to one or more letters, it will become the smallest of them (favoring &quot;a&quot; over &quot;b&quot;, etc.).  The newlines that were turned to ~ characters are preserved by detecting their indexes with the modulus operator. The padding row at the end isn't updated in the list comprehension (because the range of indexes, r, was calculated before they were added to s). Instead, a fresh row of ~ characters is added after the comprehension is done. Note that s becomes a list of characters rather than a string after first pass of the loop (but because Python is flexible about types we can still index to get at the characters in the same way).
The last line hollows out the insides of the diagram and rebuilds the characters into a string to be printed. First, any letter that is surrounded only by other copies of itself (or ~ characters from the padding) gets replaced by .. Next, the characters are all concatenated together into a single string. Finally, the padding ~ characters are converted back to newlines and the string is printed.