Соедините три королевства

Sep 11 2020

Вы - средневековый повелитель, которому поручено разработать дорожную сеть между тремя королевствами, расположенными на \$9 \times 9\$сетка. Примерное расположение королевств может выглядеть так:

^{Некоммерческое использование тайлсета доутейгами . Благодаря!}

Королевства выдвигают следующие три требования:

Дорожная сеть должна быть соединена : для любой плитки на дорожной сети, вы должны быть в состоянии достигнуть любой другой плитки на дорожной сети, просто перемещение по горизонтали или по вертикали только вдоль дорожных плиток.
В царствах должны быть соединены : всякое царство , имеет по крайней мере одну дорожную плитку непосредственно рядом по горизонтали или по вертикали.
Дорожная сеть не должна быть тонкой : Нет блок \$2\times2\$ квадраты могут быть дорожными плитками.

Обе следующие дорожные сети удовлетворяют всем трем критериям:

Следующие настройки не удовлетворяют одному из трех критериев:

Вызов

Введите \$9\times9\$сетка с тремя царствами в любом формате. Это может быть многострочная строка с пробелами и символами, список однострочных строк, список нулей и единиц, матрица или любой другой приемлемый формат для вашего языка.

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

Царства никогда не будут смежными по горизонтали или вертикали.
Нет требования, чтобы ваша дорожная сеть была минимальной в любом смысле, просто она должна соответствовать трем правилам.
Вы не можете размещать дороги на вершинах королевств.
А \$2\times2\$блок, где три плитки - дорога, а одна - королевство - ОК; третье ограничение касается только четырех дорожных плиток.

Тестовые кейсы

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

Input     -> Possible output

.........    .........
....k....    ....k....
.........    ....#....
.........    ....#....
.k....... -> .k####...
.........    .....#...
.....k...    .....k...
.........    .........
.........    .........

k.k......    k#k...... 
.........    .#.......
k........    k#.......
.........    .........
......... -> .........
.........    .........
.........    .........
.........    .........
.........    .........

.k.......    .k....... 
k........    k#.......
.k.......    .k.......
.........    .........
......... -> .........
.........    .........
.........    .........
.........    .........
.........    .........

.........    ......... 
.........    .........
k........    k#.......
.........    .#.......
k........ -> k#.......
.........    .#.......
k........    k#.......
.........    .........
.........    .........

........k    ...#####k 
....k....    ...#k....
.........    ...#.....
.........    ...#.....
......... -> ...#.....
.........    ####.....
.........    ...#.....
....k....    ...#k....
.........    ...#.....

.........    ......... 
.........    .........
.........    .........
.........    .........
......... -> .........
.........    .........
k........    k........
.k.......    #k.......
..k......    ##k......

Вот входные данные в виде списка списков, если вы предпочитаете это:

[[[0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 1, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0]], [[1, 0, 1, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0]], [[0, 1, 0, 0, 0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0]], [[0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0]], [[0, 0, 0, 0, 0, 0, 0, 0, 1], [0, 0, 0, 0, 1, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0]], [[0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0, 0, 0, 0], [0, 0, 1, 0, 0, 0, 0, 0, 0]]]

Подсчет очков

Самый короткий код в байтах побеждает.

Ответы

12 Arnauld Sep 11 2020 at 23:20

JavaScript (ES7), 166 153 149 137 байт

Медленнее и даже менее тонко, чем мой первый ответ, но и короче. Это просто ищет путь, касающийся всех царств, без создания \$2\times 2\$ дорожные блоки.

Принимает входные данные как плоский список из 81 записи с \$0\$для пустой ячейки и \$2\$для королевства. Возвращает другой список с \$0\$для пустой ячейки \$1\$для дороги и \$3\$ для королевства.

f=(a,X)=>+(z=/.*1,1.{15}1,1|2/.exec(a))?a.some((v,x)=>(a[x]++,(d=(x-X)**2)-1|x/9^X/9&&d-81?0:v?1/X&&v==2?f(a,X):0:f(a,x))||!a[x]--)&&a:!z

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

Как?

Мы используем регулярное выражение /.*1,1.{15}1,1|2/для обнаружения либо \$2\times 2\$блок дорог или оставшееся королевство. Мы получаем, nullесли ничего не найдено, строку, которая приводится к NaN унарным, +если блок сопоставлен, или строку, которая приводится к \$2\$ если соответствует королевство.

Поскольку левая и правая границы игнорируются, условие на дорожном блоке является немного более строгим, чем должно быть на самом деле, поскольку оно также будет соответствовать примерно такому:

.........
........X
X.......X
X........
.........

Тем не менее, у нас есть достаточно места, чтобы найти путь, который будет работать даже без такого шаблона.

JavaScript (ES7), 243 236 226 байт

Я не очень доволен этим методом, так как он сильно зависит от поиска методом перебора. Должны существовать более элегантные и простые способы решения этой проблемы. Но это работает!

Ожидает матрицу с \$0\$для пустой ячейки и \$3\$для королевства. Возвращает другую матрицу с \$0\$для пустой ячейки \$2\$для королевства и \$4\$ для дороги.

f=(m,k)=>(M=m.map((r,y)=>r.map((v,x)=>x^k%8&&x^k%8+2+k/8%8&&y^(q=k/64&7)&&y^q+2+k/512?v:v?3:(X=x,Y=y,1))),g=(X,Y)=>M.map((r,y)=>r.map((v,x)=>(x-X)**2+(y-Y)**2-1?0:v-1?v-3?0:r[x]=2:g(x,y,r[x]=4))))(X,Y)|/1|3/.test(M)?f(m,-~k):M

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

Как?

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

^{1: это было подтверждено эмпирически}

Пример:

Учитывая \$k\ge 0\$, мы вычисляем:

$$x_0=k\bmod 8$$ $$x_1=x_0+2+(\lfloor k/8\rfloor \bmod 8)$$ $$y_0=\lfloor k/64\rfloor \bmod 8$$ $$y_1=y_0+2+\lfloor k/512\rfloor$$

Ставим вертикальные дороги на \$x_0\$и \$x_1\$и горизонтальные дороги в \$y_0\$и \$y_1\$. Если какое-либо значение больше \$8\$, это просто игнорируется.

Потому что \$x_1\ge x_0+2\$и \$y_1\ge y_0+2\$, мы никогда не закончим мы \$2\times 2\$ блок дорог.

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

8 KjetilS. Sep 11 2020 at 21:47

Perl 5 , 251 317 298 258 байт

sub f{eval'forP(0..80){forT(0,1){my@r;forK(@_){X=intP/9;Y=P%9;I=intK/9;J=K%9;push@r,X*9+Y andT&&Y-J?Y-=Y<=>J:X-I?X-=X<=>I:Y-J?Y-=Y<=>J:0 whileX.Y neI.J}D="."x81;substrD,$_,1,1for@_;substrD,$_,1,0for@r;3==D=~y/1/1/&&D!~/00.{7}00/&&returnD}}'=~s/[A-Z]/\$$&/gr}

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

В некоторой степени безголовый:

sub f {
  for$p(0..80){              #loop through all possible starting points p,
                             #... the crossroads in the 9x9 board
                             #... from which each road to each kingdom starts
   for$t(0,1){ #for each starting point, try two strategies #...of movement: vertical first or horizontal first my @r; #init list of road tiles to empty for(@_){ #loop through all the three kingdoms from input $x=int$p/9; $y=$p%9; #x,y = start roads at current starting point p $X=int$_/9; $Y=$_%9; #X,Y = current kingdom push @r, $x*9+$y #register road tile while x,y not yet reached X,Y and # move x,y towards X,Y $t && $y-$Y ? $y-=$y<=>$Y : $x-$X ? $x-=$x<=>$X :
            $y-$Y ? $y-=$y<=>$Y :0 # move horizontally or vertically first # ...depending on current strategy t=0 or 1 while $x.$y ne $X.$Y # continue towards current kingdom unless there } $d='.'x81;                 # init current board string of 81 dots
    substr $d,$_,1,1 for @_;   # put 1's at kingdoms
    substr $d,$_,1,0 for @r;   # put 0's at road tiles
    3==$d=~s/1/1/g # if board has 3 kingdoms (none overrun by road) && $d!~/00.{7}00/        # and current board has no 2x2 road tiles
      && return $d             # then the board is valid and is returned
                               # otherwise try the next of the 81 starting points
  }
 }
}

Может работать так:

@test=( [[1,4], [4,1], [6,5]],
        [[0,0], [0,2], [2,0]],
        [[0,1], [1,0], [2,1]],
        [[2,0], [4,0], [6,0]],
        [[0,8], [1,4], [7,4]],
        [[6,0], [7,1], [8,2]] );
for(@test){
    my @kingdom = map $$_[0]*9+$$_[1], @$_;
    print display( f(@kingdom) );
}
sub display{join('',map join(' ',split//)."\n",pop=~y/10/k#/r=~/.{9}/g).('-'x17)."\n"}

Первые строки вывода: (подробнее см. Ссылку « Попробовать онлайн » выше)

# . . . . . . . .
# # # # k . . . .
# . . . . . . . .
# . . . . . . . .
# k . . . . . . .
# . . . . . . . .
# # # # # k . . .
. . . . . . . . .
. . . . . . . . .

6 xash Sep 12 2020 at 00:39

Брахилог , ⁹⁷ 93 байта

Это на самом деле быстро - грубая сила в Брахилоге! Вы не можете поверить, как я был удивлен, когда продолжал увеличивать размер доски. Однако это предполагает, что дорога не требует развилки. Если кто-нибудь найдет контрпример - предупреждаю, другая версия на TIO не запустится вовремя! :-)

Принимает замки как 2 и возвращает дороги как 1.

∧ċ{Ċℕᵐ≤ᵛ⁹}ᵐ{s₂{;.\-ᵐȧᵐ+1∧}ᵈ}ᵇP{,1↻₁}ᵐX&{iiʰgᵗc}ᶠT{ṗʰb}ˢ{,.≠&↰₃ᵐ∈ᵛ}P∧T,X≜bᵍtᵐhᵐḍ₉.¬{s₂\s₂c=₁}∧

Попробуйте онлайн! или Попробуйте все тесты!

Как работает оригинальная версия

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

ċ{l₂ℕᵐ≤ᵛ⁹}ᵐ

Ищем путь: список координат, каждая 0 ≤ X ≤ 9.

s₂ᵇ{\-ᵐȧᵐ+}ᵛ¹hᵐ

И каждая пара последовательных координат имеет расстояние 1.

P{,1↻₁}ᵐX

Мы будем хранить путь как P, а версию с 1 перед каждой координатой как X.

&{iiʰgᵗc}ᶠT

Преобразуйте матрицу в список [Type, Y, X]и сохраните его как T.

{ṗʰb}ˢ

Однако нас пока интересуют только города, поэтому они Typeдолжны быть простыми (поэтому они отмечены цифрой 2).

C,P≠

Координаты города и пути должны отличаться друг от друга.

∧C{;.↰₂1∧}ᵐ∈ᵛP≜

Каждая координата города, смещенная на 1, должна быть на пути.

∧T,Xbᵍtᵐhᵐḍ₉

Чтобы Tдобавить плитки X(путь с Type = 1добавлением в начале), сгруппируйте плитки по их координатам и возьмите последнюю - так дороги будут перезаписывать пустые плитки. Сократите список до Typeразмера и разделите его на матрицу 9x9.

.¬{s₂\\s₂c=₁}∧

Это уже результат, но убедитесь, что нет подматрицы дорог 2x2.

6 DominicvanEssen Sep 12 2020 at 19:19

R , 248 257 251 264 250 245 байт

Изменить: +9 байтов, чтобы исправить угловой регистр (буквально; см. # 1 ниже), затем немного игры в гольф, затем +13 байтов, чтобы исправить другой угловой случай (# 2, ниже), затем еще немного игры в гольф ...

function(g,s=setdiff,S=0:8%/%3-1,`^`=`%in%`){k=which(g>0,T);v=k[,1];w=k[,2]
g[r<-max(s(v+S,v)%%9),]=g[,c<-max(s(w+S,w)%%9)]=1
for(i in 1:3){x=v[i];y=w[i]
if(!(x^(r+S)|y^(c+S)))`if`(F|x^v[-i],g[x:r,y--y^w[-i]**(y<2)]<-1,g[x,y:c]<-F<-1)}
g[k]=2;g}

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

Это «конструктивное», а не «грубое» решение: мы строим единый набор дорог таким образом, чтобы условия были удовлетворены, вместо того, чтобы пробовать различные возможности и проверять, действительно ли мы нарушили одно или несколько условий.

Вход - это матрица с ненулевыми элементами, представляющая три царства. Результатом является матрица с дорогами, представленными 1, а королевства - 2.

Как?

Сначала мы строим «главные» дороги в форме «+» с севера на юг и с востока на запад через пустые элементы сетки и касаемся хотя бы одного из 3 королевств ( будьте осторожны: угол - случай 2 был, когда все королевства находятся в крайних рядах / столбцах, поэтому нам нужно убедиться, что наши «соседние» дороги все еще находятся в сетке ).
Теперь осталось не более 2 королевств, которые еще нужно связать.
Для каждого королевства, которое еще не подключено к «главным» дорогам, мы строим «подъездную дорогу» от королевства к одной из «главных» дорог.
Мы должны быть осторожны, чтобы «подъездная дорога» не была разделена одним из королевств: поэтому мы проверяем, находится ли несвязанное королевство в том же ряду, что и другое королевство, и, если это не так, мы строим подъездная дорога восток-запад. Если неподключенное королевство делит свой ряд с другим королевством, мы проверяем, разделяет ли оно также свой столбец: если нет, мы строим подъездную дорогу с севера на юг. Если это так (и он также имеет общую строку), то мы можем быть уверены, что соседние столбцы пусты, поэтому мы строим подъездную дорогу с севера на юг в столбце, примыкающем к королевству ( угловой случай 1: для этого нам нужно чтобы проверить, находится ли королевство в столбце 1: если это так, мы строим подъездную дорогу в столбце 2, иначе в столбце y-1 ).

Вот дороги (оранжевые), построенные для каждого из 6 тестовых случаев (королевства обозначены белым цветом):

Прокомментированный код:

function(g,                     # g=input grid with kingdoms
 s=setdiff,                     # s=alias to 'setdiff()' function
 S=0:8%/%3-1,                   # S=defines adjacent indices 
 `^`=`%in%`){                   # ^=alias to '%in%' function
 k=which(g>0,T)                 # k=get indices of the kingdoms
 v=k[,1];w=k[,2]                # v=x-coordinates, w=y-coordinates of kingdoms
 r<-max(s(v+S,v)%%9)            # r=empty row next-to a kingdom
                                # (elements of v±1 that are different to v, avoiding zero and >8)
 c<-max(s(w+S,w)%%9)            # c=first empty column next-to a kingdom
 g[r,]=g[,c]=1                  # build the 'main' roads
 for(i in 1:3){                 # loop through each of the 3 kingdoms:
  x=v[i];y=w[i]                 #  (x,y=x- and y-coordinates of current kingdom)
  if(!(xin%(r+S)|y%in%(c+S)))   #  if x or y are not adjacent to r or s 
                                #  (so this kingdom isn't connected to the 'main' roads)
   `if`(F|x%in%v[-i],           #  if x is shared with the row of another kingdom, or
                                #  'F' indicates that we've already built an east-west 'access road':
    g[x:r,y                     #   build an north-south 'access road' from x to r
    -                           #   (either on the same row, y, or on an adjacent row
    (-(y%in%w[-i]))**(y<2)<-1,  #   if y is shared with the col of another kingdom);
    g[x,y:c]<-F<-1)             #  otherwise build an east-west 'access road' from y to c
  }
 g[k]=2;                        # mark the kingdoms on the grid
 g                              # and return the grid
}

4 Neil Sep 12 2020 at 07:11

Уголь , 196 байт

≔Ｅ⁹ＳθＦ⁹Ｆ⌕Ａ§θιk⊞υ⟦ικ⟧ＦυＦ⁴Ｆ⁴«θＪ§ι¹§ι⁰Ｍ✳⊗λ≔⁰ζＷ⁼ＫＫ.«✳⊗κ#≦⊕ζ»≔ωηＦ⁻υ⟦ι⟧Ｆ⁴Ｆ⁴«Ｊ§μ¹§μ⁰Ｍ✳⊗ξ≔ＫＤ⁹✳⊗νδＭ⌕δ#✳⊗ν¿∧№δ#¬№…δ⌕δ#¦k¿⁼⌕υμ¬⌕υι≔⟦μⅈⅉν⌕δ#ξ⟧η¿∧η⊖ΣＥ⟦ⅈⅉ⟧↔⁻π§η⊕ρ≔⟦⟦ικζλ⟧η⟦μν⌕δ#ξ⟧⟧ε»⎚»θＦε«Ｊ⊟§ι⁰⊟§ι⁰Ｍ✳⊗⊟ι✳⊗⊟ι×#⊟ι

Попробуйте онлайн! Ссылка на подробную версию кода. Работает, рисуя линию от квадрата, прилегающего к одному королевству, к краю сетки, затем рисуя линии из квадратов, прилегающих к каждому из других королевств, чтобы пересекать первую линию, за исключением того, что две линии не могут быть точно на один ряд. Пояснение:

≔Ｅ⁹Ｓθ

Введите сетку.

Ｆ⁹Ｆ⌕Ａ§θιk⊞υ⟦ικ⟧

Найдите все королевства.

ＦυＦ⁴Ｆ⁴«

Пройдите по каждому направлению от каждого квадрата, примыкающего к каждому королевству.

θ

Распечатайте сетку.

Ｊ§ι¹§ι⁰Ｍ✳⊗λ

Перейти в выбранное королевство и перейти на выбранный соседний квадрат.

≔⁰ζ

Подсчитайте количество пустых квадратов.

Ｗ⁼ＫＫ.«

Повторить, пока текущий квадрат пуст ...

✳⊗κ#

... отметьте это #...

≦⊕ζ

... и увеличиваем счет.

»≔ωη

Начните без очереди для второго королевства.

Ｆ⁻υ⟦ι⟧

Прокрутите оставшиеся королевства.

Ｆ⁴Ｆ⁴«

Прокрутите каждое направление от каждого квадрата, прилегающего к этому королевству.

Ｊ§μ¹§μ⁰Ｍ✳⊗ξ

Перейти в это королевство и перейти на выбранную соседнюю клетку.

≔ＫＤ⁹✳⊗νδ

Захватите линию в выбранном направлении.

Ｍ⌕δ#✳⊗ν

Переместитесь туда, где линия пересекалась бы, если бы она действительна.

¿∧№δ#¬№…δ⌕δ#¦k

Эта линия пересекает линию первого королевства? Если так:

¿⁼⌕υμ¬⌕υι

Если это линия второго королевства ...

≔⟦μⅈⅉν⌕δ#ξ⟧η

... затем сохраните это как свою строку.

¿∧η⊖ΣＥ⟦ⅈⅉ⟧↔⁻π§η⊕ρ

В противном случае, если линия второго королевства не пересекает ровно один квадрат ...

≔⟦⟦ικζλ⟧η⟦μν⌕δ#ξ⟧⟧ε

... затем сохраните это как решение.

»⎚

Очистите холст, готовый к следующему соседнему квадрату первого королевства или последнему выходу.

»θ

Распечатайте сетку.

Ｆε«

Пройдите по королевствам в последнем найденном решении.

Ｊ⊟§ι⁰⊟§ι⁰Ｍ✳⊗⊟ι

Перейти на позицию королевства и перейти к найденному соседнему квадрату.

✳⊗⊟ι×#⊟ι

Распечатайте найденную строку.

Обратите внимание, что этот код пробует все комбинации царств и направлений. Вероятно, нет необходимости пробовать их все, например, я думаю, что вполне вероятно, что вы всегда можете провести линию вверх с одной из трех сторон самого нижнего королевства и соединить два других королевства с этой линией. Если это так, то код можно упростить, сэкономив в настоящее время 10 24 байта: попробуйте онлайн! Ссылка на подробную версию кода. Пояснение:

≔Ｅ⁹ＳθＦ⁹Ｆ⌕Ａ§θιk⊞υ⟦ικ⟧

Введите сетку и найдите все королевства.

≔⊟υτ

Получите самое нижнее королевство.

Ｆ³«

Проверьте квадраты справа, сверху и слева.

θＪ§τ¹§τ⁰Ｍ✳⊗ι

Распечатайте сетку и перейдите к выбранному соседнему квадрату.

≔⁰ζＷ⁼ＫＫ.«↑#≦⊕ζ»

Нарисуйте линию как можно дальше.

≔ωη

Начните без очереди для второго королевства.

ＦυＦ⁴Ｆ⁴«

Переберите два других королевства, учитывая все линии для всех четырех соседних квадратов. (Я мог бы просто использовать левую и правую строчки, но оказалось, что все строчки лучше.)

Ｊ§κ¹§κ⁰Ｍ✳⊗μ

Прыгайте на прилегающую площадь этого королевства.

≔ＫＤ⁹✳⊗λδ

Захватите линию в выбранном направлении.

¿∧№δ#¬№…δ⌕δ#¦k

Эта линия пересекает линию первого королевства? Если так:

¿⌕υκ«

Если это линия третьего королевства, то ...

¿∧η⊖↔⁻ⅉ§η¹

... если линия второго королевства не на расстоянии одного ряда, то ...

≔⟦⟦τ¹ζι⟧η⟦κλ⌕δ#μ⟧⟧ε

... сохраните это как решение.

»≔⟦κⅉλ⌕δ#μ⟧η

В противном случае для второго королевства сохраните это как свою линию.

»⎚

Очистите холст, готовый к следующему соседнему квадрату первого королевства или последнему выходу.

»θＦε«Ｊ⊟§ι⁰⊟§ι⁰Ｍ✳⊗⊟ι✳⊗⊟ι×#⊟ι

Распечатайте решение.

2 xash Sep 13 2020 at 04:23

J , ¹³⁹ 127 байт

Начиная с двух сеток [0,1]или [0,2]формируя их

#XX#… and .X.#…
#.#.…     ####…
####…     .#.#…
#.#.…     ####…

по крайней мере, одна из трех попыток будет успешной (на основе взломанного J-скрипта). Для сохранения некоторого байта это пытается еще несколько сеток:

+u({.@\:#@~.@,"3)0|:(d|.!.0]*1+i.@$)*"2/u=:(}:"2}:"{d|.10$#:1023 682)(2=_(d=:(,-)#:i.3)&(*@]*[:>./|.!.0)(9 9$!.1]1 2 2)*1=+)"2]

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

Как это примерно работает

Еще должно быть несколько байтов для гольфа. Но сейчас:

(}:"2}:"{d|.10$#:1023 682)

Сетка - сначала как матрица 10x10, чтобы мы могли легко перемещаться по 4 dнаправлениям, которые мы определим позже. Недостаток: приходится урезать до 9х9. Теперь для каждой сетки:

(9 9$!.1]1 2 2)*1=+

Когда замок находится на дороге, ставьте плитку пустой. Кроме того , дают дороги на [0,1]и [0,2]значение 2 (если они существуют). Оттуда мы найдем самую большую сеть дорог с подключением к сети:

 2=_(d=:(,-)#:i.3)&(*@]*[:>./|.!.0)

Пока карта не изменится: переместите ее и присвойте каждой дороге новый номер дороги: максимальное из текущего номера и количество соединенных дорог (но оставьте 0 как 0). Наконец, оставьте дороги отмеченными цифрой 2 - они связаны с начальными узлами.

(d|.!.0]*1+i.@$)*"2/

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

 +u({.@\:#@~.@,"3)0|:

Отсортируйте сетки по количеству соединенных замков (уникальные числа после сдвинутых номеров замков умножаются на единицы дорожной сети). Возьмите лучшую, добавьте замки обратно - и вуаля, королевство для вас!

2 Neil Sep 13 2020 at 07:47

Уголь , 67 байт

Ｆ⁹Ｆ⌕ＡＳk⊞υ⟦ικ⟧Ｂ⁹ψＦ⁹Ｆ⁹«Ｊκι¿¬№﹪⟦ικ⟧²﹪ΠＥυΠ⊕λ² »Ｆυ«Ｊ⊟ι⊟ιk»Ｆ³Ｆ³«Ｊ⁺³κ⁺³ι¤#

Попробуйте онлайн! Ссылка на подробную версию кода. Выводится с использованием пробелов для пустых плиток, но все, кроме kпустого, на входе. Это совершенно другой подход к моему предыдущему ответу, поэтому я подумал, что он заслуживает отдельного ответа. Он основан на наблюдении, что сетка с 16 отверстиями решает все проблемы, за исключением тех, у которых есть три поля рядом с углами. Все эти проблемы объединяет то, что все три царства лежат на четных строках и столбцах. В таких случаях сетка смещается по диагонали, в результате получается сетка с 25 отверстиями. Пояснение:

Ｆ⁹Ｆ⌕ＡＳk⊞υ⟦ικ⟧

Прочтите в сетке и сохраните координаты королевств.

Ｂ⁹ψ

Подготовьте пустое место для сетки.

Ｆ⁹Ｆ⁹

Пройдитесь по каждому квадрату сетки.

«Ｊκι

Перейти в эту позицию.

¿¬№﹪⟦ικ⟧²﹪ΠＥυΠ⊕λ² »

Если и строка, и столбец имеют ту же четность, что и побитовое ИЛИ для всех координат, тогда поместите явный пробел в эту позицию, чтобы предотвратить его заливное заполнение. Поскольку у меня нет хорошего способа выполнить побитовое ИЛИ списка, я использую законы Де Моргана, чтобы проверить, не содержат ли ни строка, ни столбец четности побитового И дополнения списка, отмечая, что для целей четности, произведение эквивалентно поразрядному И, а приращение эквивалентно дополнению.

Ｆυ«Ｊ⊟ι⊟ιk»

Разместите королевства на сетке.

Ｆ³Ｆ³«Ｊ⁺³κ⁺³ι¤#

Попробуйте заполнить заливкой, начиная с каждого из девяти центральных квадратов. Это гарантирует, что в результате получится единственная соединенная дорога. Только три королевства не могут отключить центр сетки, так что это всегда безопасно.

2 NahuelFouilleul Sep 14 2020 at 02:17

Perl 5 `-00ap` , 114 , 109 байт

$_|=substr'iiiiiiiii
iaiaiaiai
'x5,10*!(grep/k/,@F[1,7]),90;1while s/(?<!i.{9})(?<!ii)i(?!iii|.{9}i.{9}i)/a/s

6 байт сохранены благодаря @DomHastings, но один потерял , чтобы исправить дело .

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

Еще один ответ perl, с другим подходом, я также поддержал другой ответ perl.

Мне приходилось исправлять несколько раз из-за некоторых случаев (помимо тех, которые указаны в вопросе), в которых это не сработало.

Решение

Идея состоит в том, чтобы начать с сетки дорог, которая почти работает, и исправить для разных случаев. Если есть королевство в квадратной области os строк: 1 или 7 (после игры в гольф), сетка выравнивается по (0,0), иначе по (0,1)

.........      #########      # # # # #
ooooooooo      # # # # #      #########
.........      #########      # # # # #
.........      # # # # #      #########
.........  ?   #########  :   # # # # #
.........      # # # # #      #########
.........      #########      # # # # #
ooooooooo      # # # # #      #########
.........      #########      # # # # #

Затем оставшиеся дороги можно исправить, удалив квадраты, когда все квадраты в четырех направлениях, эмпирически (еще нет доказательства), на расстоянии 3 (справа), 2 (слева, внизу) или 1 (вверх), не являются дорогой (или находятся вне карты).