Заполнение коня - это заполнение при помощи соединения шахматной фигуры коня. В частности:

 1 1
1   1
  0
1   1
 1 1

(0 - начальная точка, 1 - подключенные ячейки)

Вызов

Учитывая двумерную сетку пространств и стен и начальное местоположение, выполните заполнение рыцаря на сетке. Самый короткий код выигрывает.

правила

• Вы можете принимать и выводить данные в любом формате, который вам нравится (изображение, строка, массив, что угодно). Вы можете взять начальное местоположение как часть входной сетки или как отдельную координату. Для целей этого объяснения будет использоваться следующий формат:

  ########    # = wall
  ########    x = initial location
  ## x  ##
  ##    ##
  ########
  ##    ##
  ########
  ########
  

• Выход - копия входной сетки с добавленным результатом заполнения рыцаря

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

  ########    # = wall
  ########    @ = fill (could also have been x)
  ## @ @##
  ## @ @##
  ########
  ##@ @ ##
  ########
  ########
  

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

• Вы можете предположить, что первоначальное местоположение никогда не будет внутри стены
• Вы можете предположить, что сетка никогда не будет больше 1000x1000
• Встроенные в порядке
• Самый короткий код (в байтах) выигрывает

Тестовые случаи

Во всех тестовых случаях #обозначает стенку, обозначает пустое пространство и xобозначает начальное местоположение заливки. @обозначает заполнение вывода.

Input 1:

########
########
## x  ##
##    ##
########
##    ##
########
########

Output 1:

########
########
## @ @##
## @ @##
########
##@ @ ##
########
########

Input 2:

############
############
## ##    x##
## ##     ##
#####     ##
##        ##
############
############

Output 2:

############
############
## ##@@@@@##
##@##@@@@@##
#####@@@@@##
## @@@@@@@##
############
############

Input 3:

####################
####################
##  ##            ##
##  ##            ##
##  ##  ########  ##
##  ##  ########  ##
##  ##  ##    ##  ##
##  ##  ##    ##  ##
##  ##  ##    ##  ##
##  ##  ##    ##  ##
##  ##  ########  ##
##  ##  ########  ##
##  ##        ##  ##
##  ##       x##  ##
##  ############  ##
##  ############  ##
##                ##
##                ##
####################
####################

Output 3:

####################
####################
##@@##@@@@@@@@@@@@##
##@@##@@@@@@@@@@@@##
##@@##@@########@@##
##@@##@@########@@##
##@@##@@##    ##@@##
##@@##@@##    ##@@##
##@@##@@##    ##@@##
##@@##@@##    ##@@##
##@@##@@########@@##
##@@##@@########@@##
##@@##@@@@@@@@##@@##
##@@##@@@@@@@@##@@##
##@@############@@##
##@@############@@##
##@@@@@@@@@@@@@@@@##
##@@@@@@@@@@@@@@@@##
####################
####################

Input 4:

################
################
##           ###
##     x     ###
##  #######  ###
##  #######  ###
##  ##   ##  ###
##  ##   ##  ###
##  ##   ##  ###
##  ########  ##
##  ########  ##
##        ##  ##
##        ##  ##
################
################

Output 4:

################
################
##   @   @   ###
## @   @   @ ###
##  #######  ###
##@ ####### @###
##  ##   ##  ###
## @##   ##@ ###
##  ##   ##  ###
##@ ########@ ##
##  ########  ##
## @   @  ## @##
##   @   @##  ##
################
################

Input 5:

##############
##############
##         ###
##         ###
##         ###
##   ###   ###
##   #x#   ###
##   ###   ###
##         ###
##         ###
##         ###
##############
##############

Output 5:

##############
##############
##@@@@@@@@@###
##@@@@@@@@@###
##@@@@@@@@@###
##@@@###@@@###
##@@@#@#@@@###
##@@@###@@@###
##@@@@@@@@@###
##@@@@@@@@@###
##@@@@@@@@@###
##############
##############

Октава, 73 байта

function a=F(s,a)do;b=a;until(a=~s&imdilate(a,de2bi(")0#0)"-31)))==b;a+=s

Демо онлайн!

* Некоторые изменения применяются для запуска в rextester.

Функция, которая принимает 2d массив 0 & 2 в качестве стены и массив 0 & 1 в качестве исходного местоположения и выводит массив 0 & 1 & 2.

JavaScript (ES6), 116 байт

f=(s,l=s.search`
`,t=s.replace(eval(`/(x| )([^]{${l-2}}(....)?|[^]{${l+l}}(..)?)(?!\\1)[x ]/`),'x$2x'))=>s==t?s:f(t)

v=(s,l=s.search`
`)=>!/^(#+)\n\1\n[^]*x[^]*\n\1\n\1$/.test(s)|s.split`
`.some(s=>s.length-l|!/^##.+##$/.test(s))&&`Invalid Input`

textarea{font-family:monospace}

<textarea rows=11 cols=33 oninput=o.value=v(this.value)||f(this.value)></textarea><textarea rows=11 cols=33 id=o reaodnly></textarea>

Основано на моем ответе « Обнаружить провальные замки» . Заполняет с помощью xs.

Python 3 , 394 387 381 356 352 347 319 313 154 139 байт

• 154 байта после подсчета только основной функции, а не функции, связанной с форматированием ввода / вывода
• сохранено 7 байт: благодаря @Jacoblaw и @ Mr.Xcoder: except:0
• сэкономил 28 байт !!!: благодаря @ovs: избавился от try: exceptблока и нескольких других гольфов
• Спасибо @Dave за прекрасный тестовый модуль.
• сохранено 6 байт: g[(a,b)]как разg[a,b]
• @nore сэкономил 15 байт !!! :

def x(g,a,b,m):
 if(a,b)in g and"!">g[a,b]or m:
  g[a,b]="@"
  for i in 1,2,-1,-2:
   for j in 3-abs(i),abs(i)-3:g=x(g,a+i,b+j,0)
 return g

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

Mathematica, 117 байт

Обычная история: мощные встроенные модули, но длинные имена ...

HighlightGraph[g,ConnectedComponents[h=Subgraph[g=KnightTourGraph@@Dimensions@#,Flatten@#~Position~1],#2]~Prepend~h]&

Попробуйте в песочнице Wolfram!

Требуется два входа: сначала входная сетка в виде массива 0s (для стен) и 1s (для пробелов), затем одно целое число для начальной позиции, найденное путем нумерации сетки вдоль строк сверху вниз, например

1  2  3  4  5
6  7  8  9  10
11 12 13 14 ...

Вы можете вызвать функцию, как HighlightGraph[...~Prepend~h]&[{{0,0,...,0}, {0,0,...,0}, ..., {0,0,...,0}}, 20].

KnightTourGraphФункция строит граф с вершинами , соответствующие позиции в сетке и ребра , соответствующие действительные движения рыцарских, то мы берем Subgraphиз вершин, которые не являются стенами, и найти ConnectedComponentsв исходной вершине. Выходные данные представляют собой график (показанный повернутым на 90 ° против часовой стрелки) с непустыми вершинами, выделенными красным, а заполненные вершины, выделенными желтым. Например, для первого тестового примера вывод выглядит так: