Krzywa jest zbiorem punktów na kwadratowej siatce, tak że każdy punkt ma dokładnie dwóch sąsiadów w sąsiedztwie z czterema sąsiadami, a punkty tworzą pojedynczy połączony komponent. Oznacza to, że wykres indukowany przez punkty na wykresie siatki jest izomorficzny dla pojedynczego cyklu. „Indukowany” oznacza, że ​​dwa punkty nie mogą dotykać wejścia bez sąsiadów w cyklu.

Antypodem wierzchołka V na wykresie jest wierzchołek najdalej oddalony od V. Antypod jest zawsze unikalny w cyklu o parzystej długości (a każdy cykl na wykresie siatki ma równą długość). Odległość mierzy się jako indukowaną przez sam cykl bez poszanowania leżącej poniżej siatki kwadratowej.

Twój wkład powinien być obrazem krzywej. Krzywa zostanie oznaczona sekwencją znaków znakowych ( #) na tle znaków spacji ( ). Jeden z punktów na krzywej zostanie oznaczony Pznakiem („pode”). Twoje dane wyjściowe będą takie same jak dane wejściowe, z tym że jeden punkt krzywej zostanie zastąpiony A(„antypode”).

Możesz założyć, że postacie zostaną wypełnione prostokątnym kształtem. Możesz założyć, że pierwszy i ostatni wiersz i kolumna danych wejściowych będą się składały wyłącznie ze spacji (dane wejściowe są wypełnione tłem). Alternatywnie możesz założyć, że pierwszy i ostatni rząd i kolumna będą zawierały punkt krzywej (wejście ma minimalne wypełnienie).

Możesz wprowadzić i wyprowadzić tę siatkę jako pojedynczy ciąg rozdzielony znakiem nowej linii, jako tablicę wierszy lub jako tablicę 2D pojedynczych znaków. Ten wybór powinien być taki sam dla wejścia i wyjścia. Jeśli Twój język na to pozwala, możesz wyprowadzać dane wyjściowe, modyfikując wprowadzone dane zamiast zwracać zmodyfikowany ciąg lub tablicę.

Możliwe dane wejściowe:

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

Odpowiednie wyniki:

P#    P##   #P#   #A###      #####P# #A#####   #####P#########   #####P#########
#A    # #   # #   #   #      #     # #     #   #             #   #             #
      ##A   #A#   ## ##      # ### # # ### #   # ### ### ### #   #             #
###                # # ###   # # # # # # # #   # # # # A # # #   #             #
# P#    ### ##A    # ### #   # # ### ### # #   # # ### ### # #   #             #
## #    # ### #    #     #   # #         # #   # #         # #   #             #
 A #    P     #    ##### P   # ########### #   # ##### ##### #   #             #
 ###    #######        ###   #             #   #     # #     #   #             #
                             ###############   ####### #######   #########A#####

Odległości wierzchołków od strąków (moduł 10) (nie wysyłaj tych):

P1    P12   1P1   5A543      54321P1 9A98765   54321P123456789   54321P123456789
1A    1 3   2 2   4   2      6     2 8     4   6             0   6             0
      23A   3A3   32 01      7 109 3 7 109 3   7 901 789 543 1   7             1
321                1 9 543   8 2 8 4 6 2 8 2   8 8 2 6 A 6 2 2   8             2
4 P1    234 89A    0 876 2   9 3 765 543 7 1   9 7 345 987 1 3   9             3
56 2    1 567 9    9     1   0 4         6 0   0 6         0 4   0             4
 A 3    P     8    87654 P   1 56789012345 9   1 54321 56789 5   1             5
 654    1234567        321   2             8   2     0 4     6   2             6
                             345678901234567   3456789 3210987   345678901A10987

JavaScript (ES6), 193 181 bajtów

f=s=>s==(`P#1P#21#12#221A`[r=`replace`](/.../g,([n,f,t])=>s=s[r](eval(`/([${n+=f}])([^]{${s.search`\n`}})?(?!\\1)[${n}]/`),m=>m[r](eval(`/^${f}|${f}$/`),t))),s)?s[r](/\d/g,`#`):f(s)

Wersja z animacją zapętloną:

f=s=>s==(`#A#1#12#221AP#1P#2`[r=`replace`](/.../g,([n,f,t])=>s=s[r](eval(`/([${n+=f}])([^]{${s.search`\n`}})?(?!\\1)[${n}]/`),m=>m[r](eval(`/^${f}|${f}$/`),t))),s)?s[r](/\d/g,`#`):s
;setInterval(_=>i.value=f(i.value),1e3)

<textarea rows=10 cols=20 id=i style="font-family:monospace"></textarea>

Python 2 , 333 221 215 bajtów

-17 bajtów dzięki @JanDvorak

g=input()
y=map(max,g).index('P')
x=g[y].index('P')
m=[k[:]for k in g]
v=x;w=y
while'#'in sum(m,[]):x,y,(v,w)=v,w,[(x+a,y+b)for a,b in((1,0),(-1,0),(0,1),(0,-1))if'#'==m[y+b][x+a]][0];m[w][v]='_'
g[w][v]='A'
print g

Wypróbuj online!

Python 3 , 402 288 282 bajtów, String IO

g=[[*k]for k in open(0).read().split('\n')]
y=[max(k)for k in g].index('P')
x=g[y].index('P')
m=[k[:]for k in g]
v=x;w=y
while'#'in sum(m,[]):x,y,(v,w)=v,w,[(x+a,y+b)for a,b in((1,0),(-1,0),(0,1),(0,-1))if'#'==m[y+b][x+a]][0];m[w][v]='_'
g[w][v]='A'
print('\n'.join(map(''.join,g)))

Wypróbuj online!

Animacja uruchomionego kodu:

MATL , 43 42 bajty

32-I#fbbJ*+!w3>y"&)yy-|&X<]vJQ2/)G65b&Zj&(

Kod akceptuje dowolną ilość dopełnienia miejsca w pierwszym i ostatnim wierszu i kolumnie. Dane wejściowe to prostokątna tablica znaków, używana ;jako separator wierszy. Na przykład dane wejściowe

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

jest reprezentowany jako

['#####   ';
 '#   #   ';
 '## ##   ';
 ' # # ###';
 ' # ### #';
 ' #     #';
 ' ##### P';
 '     ###']

lub w jednym wierszu (aby można go było wprowadzić przez STDIN),

['#####   '; '#   #   '; '## ##   '; ' # # ###'; ' # ### #'; ' #     #'; ' ##### P'; '     ###']

Wypróbuj online! Lub sprawdź ostatnie cztery przypadki: 1 , 2 , 3 , 4 (zostały wybrane, ponieważ mają najbardziej skomplikowane krzywe; ostatni ma trochę wypełnienia spacją).

Wyjaśnienie

TL; WR: Liczby zespolone, dużo indeksowania, brak splotu.

32-     % Implicitly input char matrix. Subtract 32. Space becomes zero
I#f     % 3-output find: pushes nonzero values, their row indices,
        % and their column indices, as column vectors
bb      % Bubble up twice, so row and column indices are on top
J*+     % Times 1j, add. This transforms row and column indices into
        % complex numbers, where real is row and imaginary is column
!       % Transpose into a row vector
w       % Swap, so vector of nonzero values is on top
3>      % Logical index of elements exceeding 3. ASCII codes of space,
        % '#' and 'P0 are 32, 35 and 80 respectively. Since 32 was
        % subtracted these became 0, 3 and 48. So the only entry with
        % value exceeding 3 is that corresponding to the original 'P'.
y"      % Do this as many times as the number of complex positions
        %   The stack now contains the vector of complex positions and an
        %   index into that vector. The index points to the complex position 
        %   to be processed next.
  &)    %   Two-output reference indexing: pushes the indexed entry and
        %   a vector with the remaining entries. This pulls off the
        %   current complex position, which is initially that of 'P'
  yy    %   Duplicate top two elements, i.e. current position and vector
        %   of remaining positions
  -|    %   Absolute differences
  &X<   %   Index of minimum. Gives the index of the complex position
        %   that is closest to the current one. In case of tie (which
        %   only happens in the first iteration) it picks the first. The 
        %   result is the index of the complex position to be processed in 
        %   the next iteration. This index will be empty if this is the last
        %   iteration.
]       % End
        % The stack now contains the complex positions as individual
        % values, starting from 'P' and sorted as per the curve; plus two 
        % empty arrays. These empty arrays have been produced by the last
        % iteration as the index for the "next" iteration and the array of
        % "remaining" complex positions
v       % Concatenate into a column vector. The empty arrays have no effect.
        % The resulting vector contains the sorted complex positions
JQ      % Push 1j and add 1
2/      % Divide by 2. This gives (1+1j)/2. When used as an index this is
        % interpreted as (1+end)/2. Since the length of the curve is even
        % this gives a non-integer number, which will be implicitly
        % rounded up (because of .5 fracctional part). As an example, for
        % length 32 this gives 16.5, which rounded becomes 17. Position 17
        % along the curve is the antipode of position 1
)       % Reference indexing. Gives the complex position of the antipode
G       % Push input char matrix again
65      % Push 65 (ASCII for 'A')
b       % Bubble up, so complex position is on top
&Zj     % Separate into real and imagimary parts, corresponding to row and
        % column indices
&(      % 4-input assignment indexing. This writes 'A' at the specified row
        % and column of the char matrix. Implicitly display

Python 3 , 421 bajtów

l,e=len,enumerate
r=open(0).read()
n=lambda x:[(x[0]-1,x[1]),(x[0]+1,x[1]),(x[0],x[1]-1),(x[0],x[1]+1)]
p=a={(i,j):y for i,x in e(r.split('\n'))for j,y in e(x)}
t=l(r.split('\n'));s=l(r.split('\n')[0])
for i in a:p=[p,i][a[i]=='P']
w=[p]
while l(w)!=r.count('#')+1:
 for x in a:
  if x in n(w[-1])and a[x]!=' 'and x not in w:w+=[x]
a[w[(l(w)+1)//2]]='A';print('\n'.join(''.join(a[j,i]for i in range(s))for j in range(t)))

Wypróbuj online!

Mathematica, 234 223 bajty

(p=Position;v=p[#,"#"|"P"];n=Length@v;q=v[[#]]&;h=FindCycle[Graph[v,Join@@Table[If[Norm[q@i-q@j]==1,q@i<->q@j,Nothing],{i,n},{j,i-1}]]][[1,#,1]]&;ReplacePart[#,h@Mod[p[Table[h@x,{x,n}],p[#,"P"][[1]]][[1,1]]+n/2,n,1]->"A"])&

Ten kod tworzy vlistę wierzchołków dla wykresu: indeksy "#"i "P". Następnie njest długość (koniecznie parzysta) iq wyodrębnia wierzchołek wejściowy (ignorując kształt pętli).

Następnie hjest funkcja, która buduje wykres z wierzchołkami w vi nieukierunkowanymi krawędziami między wierzchołkami, gdy długość różnicy ich par indeksów wynosi dokładnie 1 (więc ich różnica jest podobna do {-1,0}lub {0,1}), a następnie znajduje listę wszystkich cykli i zapewnia pierwszy (tylko) cykl (jako lista krawędzi), a następnie pobiera wejściową krawędź i pobiera pierwszy wierzchołek tworzący tę krawędź.

Używając h, możemy znaleźć indeks "P"cyklu i przejść do połowy (używając Modu do zawinięcia, jeśli przekroczymy granice listy cyklów), aby znaleźć antypod, a następnie możemy zastąpić odpowiedni wpis oryginału wprowadź za mpomocą"A"

Możesz wypróbować online , wklejając następujące elementy w piaskownicy chmurowej Wolfram i klikając „oceniaj komórkę” lub naciskając Shift + Enter lub Numpad Enter:

(p=Position;v=p[#,"#"|"P"];n=Length@v;q=v[[#]]&;h=FindCycle[Graph[v,Join@@Table[If[Norm[q@i-q@j]==1,q@i<->q@j,Nothing],{i,n},{j,i-1}]]][[1,#,1]]&;ReplacePart[#,h@Mod[p[Table[h@x,{x,n}],p[#,"P"][[1]]][[1,1]]+n/2,n,1]->"A"])&@{{"#","#","#","#","#"," "," "," "},{"#"," "," "," ","#"," "," "," "},{"#","#"," ","#","#"," "," "," "},{" ","#"," ","#"," ","#","#","#"},{" ","#"," ","#","#","#"," ","#"},{" ","#"," "," "," "," "," ","#"},{" ","#","#","#","#","#"," ","P"},{" "," "," "," "," ","#","#","#"}}//MatrixForm

Alternatywny pomysł, 258 bajtów

Nieznacznie zainspirowany rozwiązaniami Python firmy ovs , próbowałem napisać kod, który nie używałby żadnych cech teorii grafów w Mathematica i po prostu ślepo obliczał odległości. Nie mogłem tego zrobić tak krótko, ale podejrzewam, że ktoś mógłby to poprawić:

f[m_]:=(x="#";t=ReplacePart;p=Position;l=t[m,p[m,"P"][[1]]->0];v=p[l,x|0];n=Length[v];q=v[[#]]&;r=l[[q[#][[1]],q[#][[2]]]]&;y=t[l,q@#->(r@#2+1)]&;Do[If[Norm[q@i-q@j]==1&&Xor[r@i==x,r@j==x],If[r@i==x,l=y[i,j],l=y[j,i]]],n,{i,n},{j,n}];t[m,p[l,n/2][[1]]->"A"])`

Ten kod jest bardzo nieefektywny. Zasadniczo, to zamienia "P"się0 , a następnie szuka "#"się obok czegoś, co nie jest "#"przez zapętlenie poprzez całą rzecz dwa razy i zastępuje je z liczb reprezentujących odległość od "P", i upewnić się, że zakończy się to robi ten proces nrazy. To nawet nie oblicza poprawnie odległości, ponieważ jedna gałąź może przejść obok antypodu, ale tylko jedna lokalizacja będzie numerowana n/2bez względu na wszystko.