Fill in the lakes, 2D

Haskell, 258 characters

a§b|a<b='*'|1<3=a
z=[-1..1]
l m=zipWith(§)m$(iterate(b.q)$b(\_ _->'9'))!!(w*h)where
 w=length m`div`h
 h=length$lines m
 q d i=max$minimum[d!!(i+x+w*y)|x<-z,y<-z]
 b f=zipWith(\n->n`divMod`w¶f n)[0..]m
 (j,i)¶g|0<i&&i<w-2&&0<j&&j<h-1=g|1<3=id
main=interact l

Example run:

$> runhaskell 2638-Lakes2D.hs <<TEST
> 8888888888
> 5664303498
> 6485322898
> 5675373666
> 7875555787
> TEST
8888888888
566*****98
6*85***898
5675*7*666
7875555787

Passes all unit tests. No arbitrary limits on size.

---

• Edit (281 → 258): don't test for stability, just iterate to the upper bound; stop passing constant argument m

Python, 483 491 characters

a=dict()
def s(n,x,y,R):
 R.add((x,y))
 r=range(-1,2)
 m=set([(x+i,y+j)for i in r for j in r if(i,j)!=(0,0)and(x+i,y+j)not in R])
 z=m-set(a.keys())
 if len(z)>0:return 1
 else:return sum(s(n,k[0],k[1],R)for k in[d for d in m-z if a[(d[0],d[1])]<=n])
i=[list(x)for x in input().strip().split('\n')]
h=len(i)
w=len(i[0])
e=range(0,w)
j=range(0,h)
for c in[(x,y)for x in e for y in j]:a[c]=int(i[c[1]][c[0]])
for y in j:print(''.join([('*',str(a[(x,y)]))[s(a[(x,y)],x,y,set())>0] for x in e]))

I'm pretty sure there's a better (and shorter) way of doing this

Python, 478 471 characters

(Not including comments. 452 450 characters not including the imports.)

import sys,itertools
i=[list(x)for x in sys.stdin.read().strip().split('\n')]
h=len(i)
w=len(i[0])
n=h*w
b=n+1
e=range(h)
d=range(w)
# j is, at first, the adjancency matrix of the graph.
# The last vertex in j is the "drain" vertex.
j=[[[b,1][(t-r)**2+(v-c)**2<=1 and i[r][c]>=i[t][v]] for t in e for v in d]+[[b,1][max([r==0,r>h-2,c==0,c>w-2])]]for r in e for c in d]+[[0]*b]
r=range(b)
for k,l,m in itertools.product(r,repeat=3):
    # This is the Floyd-Warshall algorithm
    if j[l][k]+j[k][m]<j[l][m]:
        j[l][m]=j[l][k]+j[k][m]
# j is now the distance matrix for the graph.
for k in r:
    if j[k][-1]>n:
        # This means that vertex k is not connected to the "drain" vertex, and is therefore flooded.
        i[k/w][k-w*(k/w)]='*'
for r in e:print(''.join(i[r]))

The idea here is that I construct a directed graph where each grid cell has its own vertex (plus one additional "drain" vertex). There is an edge in the graph from each higher valued cell to its neighboring lower valued cells, plus there is an edge from all exterior cells to the "drain" vertex. I then use Floyd-Warshall to calculate which vertices are connected to the "drain" vertex; any vertices that are not connected will be flooded and are drawn with an asterisk.

I don't have much experience with condensing Python code, so there's probably a more succinct way I could have implemented this method.