^{Это второй из серии испытаний Island Golf. Предыдущий вызов}

Два отшельника прибыли на необитаемый остров. Поскольку они пришли искать уединения, они хотят жить как можно дальше друг от друга. Где они должны строить свои хижины, чтобы максимизировать расстояние между ними?

Связанное чтение

вход

Ваш ввод будет прямоугольной сеткой, состоящей из двух символов, представляющих землю и воду. В приведенных ниже примерах земля есть, #а вода есть ., но вы можете заменить любые два разных символа по вашему желанию.

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

Там всегда будет как минимум две плитки земли. Плитки земли все будут смежными (то есть есть только один остров). Водяные плитки также будут смежными (т.е. там нет озер). Внешняя граница сетки будет водяной плиткой. Плитки земли не будут связаны по диагонали: то есть вы никогда не увидите ничего подобного

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

Выход

Ваш код должен выводить ту же сетку с двумя отмеченными местоположениями хижины . В приведенных ниже примерах местоположения хижины помечены знаком X, но вы можете заменить любого персонажа, если он отличается от ваших символов земли и воды.

Места хижины должны быть двумя плитками земли, выбранными таким образом, чтобы максимизировать расстояние между ними. Мы определяем расстояние ходьбы как длину кратчайшего пути, полностью на суше, между двумя точками. Наземные плитки считаются смежными по горизонтали или вертикали, но не по диагонали.

Возможное решение для вышеуказанного острова:

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

Пешком между этими двумя точками является 11, что является наибольшим расстоянием между любыми двумя точками на этом острове. Существует еще одно решение дистанции 11:

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

Детали

Ваше решение может быть полной программой или функцией . Любой из методов ввода и вывода по умолчанию является приемлемым.

Ваш ввод и вывод может быть многострочной строкой, списком строк или двумерным массивом / вложенным списком символов / односимвольных строк. Ваш вывод может (опционально) иметь один завершающий перевод строки. Как упоминалось выше, вы можете использовать любые три различных символа вместо #.X(пожалуйста, укажите в своем представлении, какие символы вы используете).

Контрольные примеры

А. Острова с уникальными местами размещения в хижине:

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

....
.XX.
....

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

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

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

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

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

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

Б. Пример острова с несколькими возможными решениями:

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

Возможные выводы:

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

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

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

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

C. Большой контрольный пример

Это код-гольф : выигрывает самый короткий код на каждом языке.

Python 3, 249 246 байт

Побрил 3 байта, спасибо DLosc.

Вход и выход - одиночные строки, где '.', '@' И 'X' представляют воду, хижины и землю соответственно.

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

Предыдущая версия:

Ввод - это одна строка с '.' и «#» представляет воду и землю соответственно. «Х» представляет хижины на выходе.

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

Объяснение:

Это в основном поиск в ширину по всем возможным отправным точкам одновременно. Сохраните словарь, d, длины пути, обозначенные началом и концом пути, например, d [(k, i)] - это расстояние от k до i. Затем перебираем ключи в словаре d и создаем новый словарь u с путями, которые на 1 единицу длиннее, перемещая конечную точку на 1 единицу в N, S, E, W, например, u [(k, i + 1)] = d [(k, i)] + 1. Не включайте пути, которые уже есть в d. Если u не пусто, добавьте новые более длинные пути к d и повторите. Когда u пусто, это означает, что больше пути не могут быть сделаны. Теперь d содержит все возможные пути и их длины. Так что это просто вопрос получения ключа с самым длинным путем.

Менее гольф, прокомментированная версия:

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 байт

Давайте запустим мяч ...

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

Попробуйте онлайн

Полная программа, читает из STDIN, пишет в STDOUT. Он просто перебирает каждую ячейку и запускает BFS для вычисления самой дальней ячейки, записывая обе, если она самая дальняя в записи. Ничего особенного, и, к сожалению, мало что я могу найти в гольфе.

Отформатированный и закомментированный код:

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
    }
}