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

вход

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

• #: Стена
• P: Заключенный
• пространство: пустое пространство

Пример ввода будет выглядеть так:

#####
#   #
# P #
#   #
#####

Выход

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

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

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

############# Truthy
# P #  P#   #
#   #   # P #
#############

############# Truthy
# P    P    #
#   #   # P #
#############

############# Falsey
# P #  P#   #
#   #   # P #
########## ##

####          Truthy
#   #
 #   #
  # P ####
  ####

P             Falsey

###           Falsey
# #
# #
### P

Улитки , 13 байт

!(t\P(o\ ),o~

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

Отпечатки 0для небезопасных тюрем и размер ограничительной рамки ввода для защищенных тюрем.

Идея состоит в том, чтобы гарантировать, что мы не сможем найти путь от Pячейки a до границы ( ~), движущейся только ортогонально ( o) через пробелы. Это tтелепорт, так что независимо от того, где мы пытаемся найти совпадение, он пытается найти все возможные исходные позиции P.

C # (.NET Core) , 485 480 474 470 421 408 байт

Абсолютно неправильный инструмент и подход, но тем не менее ...

• 7 байт (и более) сохранены с полезными советами от TheLethalCoder.
• 4 байта сохраняются путем возврата целого числа.
• Еще 4 байта спасены благодаря (еще раз) , чтобы TheLethalCoder путем замены ' 'с 32в сравнениях.
• МНОГО байтов, сохраненных путем рефакторинга кода.
• Еще 13 байтов благодаря (угадайте кто?) TheLethalCoder. :) Я постоянно забываю его советы, и он продолжает напоминать мне их.

m=>{var p='P';int a=m.Length,b=m[0].Length,i=0,j,x,y;var c=new System.Collections.Stack();for(;i<a;i++)for(j=0;j<b;j++)if(m[i][j]==p)c.Push(new[]{i,j});while(c.Count>0){var t=(int[])c.Pop();x=t[0];y=t[1];if(x<1|x>a-2|y<1|y>b-2)return 0;foreach(var v in new[]{-1,1}){var z=x>0&x<a-1&y>0&y<b-1;if(z&m[x+v][y]==32){m[x][y]=p;c.Push(new[]{x+v,y});}if(z&m[x][y+v]==32){m[x][y]=p;c.Push(new[]{x,y+v});}}}return 1;}

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

По сути, я расширяю позиции P всякий раз, когда появляется белое пространство, пока оно не достигнет (или не достигнет) границы макета.

Некоторые лицензии:

• Я использую char[][]как вход для макета.
• Возвращает 0как небезопасные и 1безопасные.

Perl 5 , 69 байт

-10 байт благодаря @Grimy .

-2 байта благодаря @Neil .

77 байт кода + -p0флаги.

/
/;$_=s/(P| )(.{@{-}})?(?!\1)(?1)/P$2P/s?redo:!/\A.*P|P.*\Z|^P|P$/m

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

Несколько коротких объяснений:
Идея заключается в том, чтобы заключить Pповсюду. Если кто-либо Pнаходится в первой / последней строке или в первом / последнем столбце, заключенные могут туда и обратно бежать, что означает, что тюрьма не защищена.
s/(P| )(.{@{-}})?(?!\1)(?1)/P$2P/sзаменяет пробел справа или ниже a Pна P, или пробел слева или сверху a P.
Наконец, /\A.*P|P.*\Z|^P|P$/mпроверяет, начинается ли строка или заканчивается ли она Pили есть ли Pв первой или последней строке.

JavaScript (ES6), 134 133 байта

Принимает ввод как массив массивов символов. Возвращает 0(небезопасно) или 1(безопасно).

f=a=>a.map((r,y)=>r.map((c,x)=>c>'O'&&[-1,1,0,0].map((X,i)=>(R=a[y+1-'1102'[i]])&&R[X+=x]?R[X]<'!'?R[o=2,X]=c:0:o=0)),o=1)|o&2?f(a):o

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

f=a=>a.map((r,y)=>r.map((c,x)=>c>'O'&&[-1,1,0,0].map((X,i)=>(R=a[y+1-'1102'[i]])&&R[X+=x]?R[X]<'!'?R[o=2,X]=c:0:o=0)),o=1)|o&2?f(a):o

console.log(f([
  [...'#############'],
  [...'# P #  P#   #'],
  [...'#   #   # P #'],
  [...'#############']
]))

console.log(f([
  [...'#############'],
  [...'# P    P    #'],
  [...'#   #   # P #'],
  [...'#############']
]))

console.log(f([
  [...'#############'],
  [...'# P #  P#   #'],
  [...'#   #   # P #'],
  [...'########## ##']
]))

console.log(f([
  [...'####'],
  [...'#   #'],
  [...' #   #'],
  [...'  # P ####'],
  [...'  ####']
]))

console.log(f([
  [...'P']
]))

console.log(f([
  [...'###'],
  [...'# #'],
  [...'# #'],
  [...'### P']
]))

JavaScript (ES6), 121 байт

f=s=>s==(s=s.replace(eval('/( |P)([^]{'+s.search`
`+'})?(?!\\1)[ P]/'),'P$2P'))?!/^.*P|P.*$/.test(s)&!/^P|P$/m.test(s):f(s)

Принимает ввод как разделенную новой строкой прямоугольную строку. Возвращает 0 для небезопасного и 1 для безопасного. Исходя из моего ответа « Обнаружить провальные замки» , хотя было бы более эффективно проверять сбежавшего заключенного на каждом этапе, а не после того, как они закончили исследовать тюрьму.

Октава, 64 55 байт

@(a,z=padarray(a,[1 1]))~nnz(bwfill(z==35,1,1,4)&z>35);

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

или же

Проверьте все контрольные примеры!

Объяснение:

z=padarray(a,[1 1])       %add a boundary(of 0s) around the scene
F = bwfill(z==35,1,1,4)   %flood fill the prison starting from the boundary
~nnz(F&z>35);             %if position of at least a prisoner  is filled then the prison is not secure 

APL (Dyalog Classic) , 40 байтов

{⊃2≠(××{1⊃⌈/⍵,⍉⍵}⌺3 3)⍣≡(⌽1,⍉)⍣4⊢'# '⍳⍵}

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

'# '⍳⍵кодирование '#', ' ', 'P'а 0 1 2

(⌽1,⍉)⍣4 окружить с 1с

(××{1⊃⌈/⍵,⍉⍵}⌺3 3)⍣≡ Заполнение max-of-соседей ненулевых ячеек

⊃2≠ у нас нет 2 вверху слева?

Stax , 35 байтов ^CP437

ä¬my■╡╤▲l@┤êr*⌠\¶ƒläå─▄¶√¿ [Uy⌠Só4↔

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

Конечно, язык игры в гольф без внутреннего, чтобы справиться с поиском пути, может сделать это также!

объяснение

Использует распакованный формат для объяснения.

zLz]Y+Mys+y+{{{" P|P ""PP"Rm}Y!My!Mgphh' =
zLz]Y+Mys+y+                                  Surround the original matrix with four borders of whitespaces
            {                      gp         Iterate until a fixed point is found, return the single fixed point
             {              }Y!               Store the block in register Y and execute it
              {" P|P ""PP"Rm                  For each row, flood every space adjacent to a P with P.
                               My!            Transpose the matrix and do the flooding again
                                     hh' =    The final matrix has a space on the upper left corner that has not been flooded by P 

SmileBASIC, 154 146 байт

Я надеялся, что ответ с использованием заливки будет короче, чем этот.

DEF S P
FOR J=0TO 1X=1Y=1FOR I=0TO LEN(P)-1GPSET X,Y,-(P[I]=="#")GPAINT X,Y,-1,-J*(P[I]>@A)X=X*(P[I]>"31")+1INC Y,X<2NEXT
NEXT?!GSPOIT(0,0)GCLS
END

Заменить 31на соответствующий символ ASCII.