Preencha os lagos, 2D

A versão unidimensional deste problema era bastante fácil, então aqui está uma versão 2D mais difícil.

Você recebe um conjunto 2D de alturas de terra com entrada padrão e precisa descobrir onde os lagos se formarão quando chover. O mapa de altura é apenas uma matriz retangular dos números de 0 a 9, inclusive.

8888888888
5664303498
6485322898
5675373666
7875555787

Você deve produzir a mesma matriz, substituindo todos os locais que estariam embaixo d'água *.

8888888888
566*****98
6*85***898
5675*7*666
7875555787

A água pode escapar na diagonal, portanto não haveria lago nesta configuração:

888
838
388

o código mais curto vence. Seu código deve lidar com tamanhos de até 80 de largura e 24 de altura.

Mais três exemplos:

77777    77777
75657    7*6*7
75757 => 7*7*7
77677    77677
77477    77477

599999    599999
933339    9****9
936639 => 9*66*9
935539    9*55*9
932109    9****9
999999    999999

88888888    88888888
84482288    8**8**88
84452233 => 8**5**33
84482288    8**8**88
88888888    88888888

Haskell, 258 caracteres

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

Exemplo de execução:

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

Passa em todos os testes de unidade. Não há limites arbitrários no tamanho.

• Editar (281 → 258): não teste a estabilidade, apenas itere para o limite superior; parar de passar argumento constantem

Python, 483 491 caracteres

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]))

Tenho certeza de que existe uma maneira melhor (e mais curta) de fazer isso

Python, 478 471 caracteres

(Sem incluir comentários. 452 450 caracteres sem incluir as importações.)

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]))

A idéia aqui é que eu construa um gráfico direcionado onde cada célula da grade tenha seu próprio vértice (mais um vértice "dreno" adicional). Há uma aresta no gráfico de cada célula de valor mais alto para as células vizinhas de valor mais baixo, além de haver uma aresta de todas as células externas no vértice "drenar". Eu então uso o Floyd-Warshall para calcular quais vértices estão conectados ao vértice "drenar"; quaisquer vértices que não estiverem conectados serão inundados e desenhados com um asterisco.

Como não tenho muita experiência com a condensação de código Python, provavelmente há uma maneira mais sucinta de implementar esse método.

Lisp comum, 833

(defun drains (terr dm a b)
  (cond
    ((= (aref dm a b) 1) t)
    ((= (aref dm a b) -1) nil)
    ((or (= a 0) (= b 0)
     (= a (1- (array-dimension terr 0)))
     (= b (1- (array-dimension terr 1)))) t)
    (t (loop for x from -1 to 1
       do (loop for y from 0 to 1
           do (if (and (or (> x 0) (> y 0))
                   (drains terr dm (+ a x) (+ b y))
                   (<= (aref terr (+ a x) (+ b y))
                   (aref terr a b)))
              (progn
                (setf (aref dm a b) 1)
                (return-from drains t)))))
    (setf (aref dm a b) -1)
    nil)))

(defun doit (terr)
  (let ((dm (make-array (array-dimensions terr))))
    (loop for x from 0 to (- (array-dimension terr 0) 1)
       do (loop for y from 0 to (- (array-dimension terr 1) 1)
         do (format t "~a"
            (if (drains terr dm x y)
                (aref terr x y)
                "*"))
         finally (format t "~%")))))

Nenhuma tentativa foi feita para jogar golfe, apenas achei o problema interessante. Entrada é a matriz 2D do mapa. A solução verifica cada quadrado para ver se "drena" - um quadrado drena se estiver na borda externa ou se estiver adjacente a um quadrado de altura igual ou inferior que drena. Para evitar recursões sem fim, o código mantém um "mapa de drenagem" (dm) onde armazena o status de drenagem dos quadrados que já foram determinados.

Python, 246 caracteres

import os
a=list(os.read(0,2e3))
w=a.index('\n')+1
a+=' '*w
def f(p,t):
    if e<a[p]or p in t:return
    t[p]=1
    return'*'>a[p]or any(f(p+d,t)for d in(~w,-w,-w+1,-1,1,w-1,w,w+1))
z=0
for e in a:
    if(' '<e)*~-f(z,{}):a[z]='*'
    z+=1
print''.join(a[:~w])

A solução funciona executando um DFS de cada posição para determinar se deve ou não ser preenchido.

Se o espaço em branco à direita em cada linha for permitido, ele poderá ser reduzido usando w = 80 e preenchendo as linhas de entrada com espaço em branco para 80 caracteres.