^{Este es el segundo de una serie de desafíos de Island Golf. Desafío anterior}

Dos ermitaños han llegado a una isla desierta. Como vinieron buscando la soledad, desean vivir lo más lejos posible el uno del otro. ¿Dónde deberían construir sus cabañas para maximizar la distancia a pie entre ellos?

Lectura relacionada

Entrada

Su entrada será una cuadrícula rectangular que consta de dos caracteres, que representan tierra y agua. En los ejemplos a continuación, la tierra es #y el agua es ., pero puede sustituir los dos caracteres distintos que desee.

...........
...##......
..#####....
..#######..
.#########.
...#######.
...#####.#.
....####...
...........

Siempre habrá al menos dos fichas de tierra. Todas las fichas de tierra serán contiguas (es decir, solo hay una isla). Las baldosas de agua también serán contiguas (es decir, no hay lagos). El borde exterior de la cuadrícula será de baldosas de agua. Las fichas de tierra no se conectarán en diagonal: es decir, nunca verás algo como

....
.#..
..#.
....

Salida

Su código debe generar la misma cuadrícula, con dos ubicaciones de cabaña marcadas en ella. En los ejemplos a continuación, las ubicaciones de la cabaña están marcadas con una X, pero puede sustituir cualquier carácter siempre que sea distinto de sus caracteres de tierra y agua.

Las ubicaciones de la cabaña deben ser dos baldosas terrestres, elegidas para maximizar la distancia a pie entre ellas. Definimos la distancia a pie como la longitud del camino más corto, enteramente en tierra, entre los dos puntos. Las baldosas terrestres se consideran adyacentes horizontal o verticalmente, pero no diagonalmente.

Una posible solución para la isla anterior:

...........
...X#......
..#####....
..#######..
.#########.
...#######.
...#####.X.
....####...
...........

La distancia a pie entre estos dos puntos es 11, que es la mayor distancia entre dos puntos en esta isla. Hay otra solución de distancia 11:

...........
...##......
..X####....
..#######..
.#########.
...#######.
...#####.X.
....####...
...........

Detalles

Su solución puede ser un programa completo o una función . Cualquiera de los métodos de entrada y salida predeterminados son aceptables.

Su entrada y salida puede ser una cadena multilínea, una lista de cadenas o una matriz 2D / lista anidada de caracteres / cadenas de un solo carácter. Su salida puede (opcionalmente) tener una nueva línea final. Como se mencionó anteriormente, puede usar tres caracteres distintos en lugar de #.X(especifique en su envío qué caracteres está usando).

Casos de prueba

A. Islas con ubicaciones únicas en cabañas:

....
.##.
....

....
.XX.
....

......
......
..##..
...#..
......
......

......
......
..X#..
...X..
......
......

........
.#####..
.##..##.
.#..###.
.##..##.
........

........
.#####..
.##..##.
.#..###.
.#X..#X.
........

.........
.#####.#.
.#...#.#.
.#.###.#.
.#.....#.
.#######.
.........

.........
.#####.X.
.#...#.#.
.#.X##.#.
.#.....#.
.#######.
.........

B. Ejemplo de una isla con múltiples soluciones posibles:

........
....##..
...####.
..###...
.#####..
.#####..
..##....
........

Salidas posibles:

........
....#X..
...####.
..###...
.#####..
.X####..
..##....
........

........
....#X..
...####.
..###...
.#####..
.#####..
..X#....
........

........
....##..
...###X.
..###...
.#####..
.X####..
..##....
........

........
....##..
...###X.
..###...
.#####..
.#####..
..X#....
........

C. Gran caso de prueba como Gist

Este es el código de golf : gana el código más corto en cada idioma.

Python 3, 249 246 bytes

Afeitado de 3 bytes, gracias DLosc.

La entrada y la salida son cadenas simples, con '.', '@' Y 'X' que representan agua, cabañas y tierra, respectivamente.

A='@'
def f(s):
 w=s.find('\n')+1;d=u={(k,k):0for k,c in enumerate(s)if A<c}
 while u:d.update(u);u={(k,j):d[(k,i)]+1for k,i in d for j in{i+1,i+w,i-1,i-w}if A<s[j]and(k,j)not in d}
 k,j=sorted(max(d,key=d.get))
 return s[:k]+A+s[k+1:j]+A+s[j+1:]

Versión anterior:

La entrada es una sola cadena, con '.' y '#' representando agua y tierra, respectivamente. 'X' representa las cabañas en la salida.

def f(s):
 w=s.find('\n')+1;d=u={(k,k):0for k,c in enumerate(s)if'#'==c}
 while u:d.update(u);u={(k,j):d[(k,i)]+1 for k,i in d for j in{i+1,i+w,i-1,i-w}if'#'==s[j]and(k,j)not in d}
 k,j=sorted(max(d,key=d.get))
 return s[:k]+'X'+s[k+1:j]+'X'+s[j+1:]

Explicación:

Básicamente se trata de una primera búsqueda amplia desde todos los puntos de partida posibles al mismo tiempo. Mantenga un diccionario, d, de las longitudes de ruta marcadas por el inicio y el final de la ruta, por ejemplo, d [(k, i)] es la distancia de k a i. Luego itere sobre las teclas en el diccionario, d, y cree un nuevo diccionario, u, con caminos que sean 1 unidad más largos moviendo el punto final 1 unidad a N, S, E, W, por ejemplo, u [(k, i + 1)] = d [(k, i)] + 1. No incluya rutas que ya están en d. Si u no está vacío, agregue las nuevas rutas más largas a d y repita. Cuando u está vacío, eso significa que no se pueden hacer más caminos. Ahora d contiene todos los caminos posibles y sus longitudes. Entonces es solo cuestión de obtener la clave con el camino más largo.

Versión menos comentada y comentada:

def f(s):
  w=s.find('\n')+1                    # width of a row, or a move N or S

  d = {}                              # dictionary of all the paths.
                                      # The key is a tuple (k,j) and the
                                      # value is the distance from k to j.
  for k,c in enumerate(s):            # Initialize. Distance from k to k is 0
    if'#'==c:                         # Only do land.
      d[(k,k)] = 0

  u = d                               # dictionary of new paths. initialize it to d
                                      # so loop is entered. first d.update is
                                      # basically a NOP

  while u:                            # while there are new paths
    d.update(u)                       # add the new paths to the dict of old paths
    u={}                              #
    for k,i in d:                     # iterate over the known paths. k is the start, i is the end
      for j in{i+1,i+w,i-1,i-w}:      # iterate over squares 1 move to the E,S,W,N from i
        if'#'==s[j]and(k,j)not in d:  # if it's still land, and the path (k,j) isn't already in d,
          u[(k,j)] = d[(k,i)]+1       # then add the new path to u

  k,j=sorted(max(d,key=d.get))        # find the longest path

  return s[:k]+'X'+s[k+1:j]+'X'+s[j+1:]  # X marks the endpoints.

C #, 387 bytes

Hagamos rodar la pelota ...

using C=System.Console;class P{static void Main(){string D="",L;int W=0,H=0,z,n,q,h,b=0,c,a,i=0,j=0;for(;(L=C.ReadLine())!=null;H+=W=L.Length)D+=L+="\n";for(z=H;z-->0;){int[]S=new int[H],Q=new int[H*8];for(Q[h=q=0]=z;q<=h;)if((c=S[n=Q[q++]]-1)<0&D[S[n]=n]==35)for(a=4;a-->0;b=c<b?c+(i=z)*(j=n)*0:b)S[Q[++h]=new[]{1,-1,W,-W}[a]+n]=S[Q[h]]<1?c:1;}for(;++z<H;)C.Write(z==i|z==j?'X':D[z]);}}

Pruébalo en línea

Programa completo, lee de STDIN, escribe en STDOUT. Simplemente pasa por cada celda y ejecuta un BFS para calcular la celda más lejana, registrando ambas si es la más lejana registrada. Nada realmente, y frustrantemente poco que puedo encontrar para jugar golf.

Código formateado y comentado:

using C=System.Console;

class P
{
    // \n 10
    // \r 13
    // . 46
    // # 35
    // x 88

    static void Main()
    {
        string D="", // map
            L; // line of input

        int W=0, // width
            H=0, // length
            z, // outer position
            n, // next position to expand
            q, // queue position pointer
            h, // queue head pointer
            b=0, // best
            c, // distance to this cell (negative)
            a, // counter
            i=0, // hermit 1 pos
            j=0; // hermit 2 pos

        for(;(L=C.ReadLine())!=null; // read a line, while we can
                H+=W=L.Length) // record the width, and add to length
            D+=L+="\n"; // add a newline, and add the line to the map

        for(z=H;z-->0;) // for each cell
        {
            int[]S=new int[H], // 'seen' >0 -> seen, else it is the distance we have found to it
                Q=new int[H*8]; // due queue (fewer than H*4 expantions, two ints each)

            // standard BFS
            for(Q[h=q=0] // reset currect 
                =z; // expand z first
                q<=h;)
                if((c=S[n=Q[q++]]-1)<0& // record 'seen', and check we havn't been seen
                    D[S[n]=n]==35) // mark as seen, and check we are a hash #
                    // 'move'
                    for(a=4;a-->0; // for each of the 4 neighbours
                            b=c<b? // if we have beaten the best
                            c+(i=z)*(j=n)*0: // set new best, record hermit positions
                            b)
                        S[Q[++h]=new[]{1,-1,W,-W}[a]+n]= // queue it for expantion
                        S[Q[h]]<1? // not seen? (this is BFS, don't need to check c is less thatn S[l+n]
                        c: // distance
                        1; // mark as seen (means it won't actually be expanded)
        }

        // z = -1
        for(;++z<H;) // for each cell
            C.Write(z==i|z==j?'X':D[z]); // print either the original char, or X if it is a hermit's home
    }
}