[Question]
  [
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](https://en.wikipedia.org/wiki/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:
![A sketch highlighting the boundaries](https://i.stack.imgur.com/1XwIQ.gif)
  
**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:
![color enhancement](https://i.stack.imgur.com/IuKCW.gif)
  
[Answer]
# Python 3 - 424 422 417 332 295 characters:
```
def v(s):
 w=s.find("\n")+1;n=(-1,1,-w,w);r=range(len(s));x=str.replace;s=x(x(s,*".~"),*"\n~")+"~"*w;t=0
 while s!=t:t=s;s=[min(s[i+j]for j in n).lower()if"~"==s[i]and(i+1)%w else s[i]for i in r]+["~"]*w
 print(x("".join(s[i]if any(s[i]!=s[i+j].lower()!="~"for j in n)else"."for i in r),*"~\n"))
```
There are three parts, each of which needs to be on its own line due to Python's syntax:
1. 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,*"xy")` to save characters, rather than the conventional `s.replace("x", "y")`). 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 "old" 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).
2. 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 `"a"` over `"b"`, 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).
3. 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.
[Answer]
### GolfScript, 138 144 137 characters
```
:^n%,,{{^n/1$=2$>1<.'.'={;{@~@+@@+\{^3$?^<n/),\,@-abs@@-abs+99*+}++^'.
'-\$1<{32+}%}++[0..1.0..(.0]2/%..&,(\0='.'if}{@@;;}if}+^n?,%puts}/
```
Input is given to the subprogram as a single string on the stack. Unfortunately I had to use a `puts` because of the requirement that the routine has to print the result.
**Explanation of the code**
The outer block essentially loops over all position (x,y) according to the size of the input rectangles. Within the loop the coordinates x and y are left on the stack each time. After each line is complete the result is printed to console.
```
:^              # save input in variable ^
n%,,{{          # split along newlines, count rows, make list [0..rows-1] 
    ???             # loop code, see below
}+^n?,%puts}/       # ^n?, count columns, make list [0..cols-1], loop and print
```
The code executed within the loop first takes the corresponding character of the input.
```
^n/                 # split input into lines
1$=                 # select the corresponding row
2$>1<               # select the corresponding col
```
Then basically we check, if we have a `.`, i.e. if we (possibly) have to replace the character.
```
.'.'={              # if the character is '.'
    ;               # throw away the '.'
    ???             # perform more code (see below)
}{                  # else
    @@;;            # remove coordinates, i.e. keep the current character 
                    # (i.e. A, B, ... or \n)
}if                 # end if
```
Again, the inner code starts with a loop, now over all coordinates (x,y) (x,y+1) (x+1,y) (x,y-1) (x-1,y)
```
{                   
    @~@+@@+\        # build coordinates x+dx, y+dy
    ???             # loop code
}++                 # push coordinates before executing loop code
[0..1.0..(.0]2/%    # loop over the coordinates [0 0] [0 1] [1 0] [0 -1] [-1 0]
```
The recent inner code snippet simply returns the (lower case) letter of the nearest point, given the two coordinates.
```
{                   # loop
    ^3$?^<          # find the current letter (A, B, ...) in the input string, 
                    # take anything before
    n/              # split at newlines
    ),              # from the last part take the length (i.e. column in which the letter is)
    \,              # count the number of lines remaining (i.e. row in which the letter is)
    @-abs@@-abs+    # calculate distance to the given coordinate x, y
    99*+            # multiply by 99 and add character value (used for sorting
                    # chars with equal distance)
}++                 # push the coordinates x, y
^'.
'-                  # remove '.' and newline
\$                  # now sort according to the code block above (i.e. by distance to letter)
1<{32+}%            # take the first one and make lowercase
```
So from the five nearest letters for the coordinates (x,y) (x,y+1) (x+1,y) (x,y-1) (x-1,y) take the first, if not all are equal, otherwise take a `.`.
```
.                   # copy five letter string
.&,(                # are there distinct letters?
\0=                 # first letter (i.e. nearest for coordinate x,y)
'.'                 # or dot
if                  # if command
```
[Answer]
## Python, 229 226 chars
```
def F(s):
 e,f,b='~.\n';N=s.index(b)+1;s=s.replace(f,e)
 for i in 2*N*e:s=''.join(min([x[0]]+[[y.lower()for y in x if y>b],all(y.lower()in f+b+x[0]for y in x)*[f]][x[0]!=e])for x in zip(s,s[1:]+b,s[N:]+b*N,b+s,b*N+s))
 print s
F("""......B..
.........
...A.....
.........
.......D.
.........
.C.......
.....E...
.........
""")
```
Does a flood fill to compute the result. The trailing `for`/`zip` combo generates an array `x` for each cell containing the value in that cell and its four neighbors. Then we use Blckknght's trick and `min` a bunch of possibilities for each cell. Those are the original cell value, any neighbors if the cell has not been visited yet, or a `.` if it has been visited and all neighbors are `.` or equal to the cell itself.
]