Chris, tajemniczy uzależniony od krzyżówek, ma ustalony algorytm, według którego je rozwiązuje.

Użyjemy powyższego obrazu jako przewodnika.

1. Chris zawsze zaczyna od pierwszej wskazówki, w tym przypadku 1 Across. Chris jest zdolnym entuzjastą krzyżówki, więc zakłada się, że zawsze pozna odpowiedź na wskazówkę, nad którą pracuje.
2. Gdy Chris ukończy wskazówkę, sprawdzi wszystkie wskazówki sąsiadujące z tymi, które ukończył (w pierwszym przypadku 1 w dół, 2 w dół i 3 w dół), a następnie ukończy wskazówkę o najniższym numerze. Jeśli nie ma żadnych sąsiednich wskazówek, przejdzie do kroku 3.
3. Jeśli wskazówka jest taka, że ​​następny numer (jak opisano w kroku 3) zawiera zarówno wskazówkę przekreśloną, jak i wskazówkę dolną, najpierw ukończy wskazówkę przekreśloną (100% pewności, to graniczy z OCD!)
4. Jeśli nie ma żadnych sąsiadujących wskazówek, przejdzie do następnej dostępnej wskazówki, która będzie następna pod względem liczby (w poprzek lub w dół)
5. Powtarzaj od kroku 2, aż wszystkie wskazówki zostaną ukończone.

I tu sprowadza się do was, drodzy koderzy. Masz za zadanie stworzyć kod, który po otrzymaniu szablonu krzyżówki może dostarczyć wyniki opisujące kolejność wskazówek opartych na algorytmie Chrisa do jego rozwiązania.

Kod zaakceptuje wprowadzenie szablonu krzyżówki w postaci .białego kwadratu i #czarnego kwadratu.

Przykład :

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

Dane wejściowe mogą odbywać się poprzez: a) odczyt pliku reprezentacji krzyżówki, lub b) wprowadzanie linii każdego wiersza krzyżówki, a następnie \ndrugie \nwskazanie EOF.

A następnie określi metodę, według której Chris rozwiąże go zgodnie z powyższym algorytmem, który opisał.

Dane wyjściowe muszą być w formacie szeregu instrukcji oddzielonych przecinkami w postaci n(A|D), gdzie njest numer wskazówki, po której następuje znak „ Aza” lub „ Dza”.

Tak więc w powyższym przykładzie (zarówno z obrazu, jak i przykładowego szablonu, które są jednym i tym samym), dane wyjściowe byłyby następujące:

1A,1D,2D,3D,9A,10A,4D,5D,6D,7D,8D,11A,12A,13A,15A,14D,15D,16A,17A,18D,19D,20A,21D,23A,22D,24A,25D,27A,28A,26D,29A,30A,31A

Najkrótszy kod wygrywa ...

Testowanie

Musisz podać swój kod, liczbę bajtów, a także jeden z czterech przypadków testowych reprezentowanych w formacie .i #, a także dane wyjściowe wygenerowane z tego wejścia. Istnieją cztery przypadki testowe, trzy poniżej oraz powyższy przykładowy szablon.

Przykładowe przypadki testowe:

Przypadek testowy 1

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

Wynik: 1A,1D,2D,3D,4A,5A,6A,7A

Przypadek testowy 2

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

Wynik: 1A,1D,2D,5A,4D,4A,3D,3A,7A,8A,6D,9A

Przypadek testowy 3

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

Wynik: 1A,2D,3D,4D,5D,7A,8A,9A,10A,11A,11D,12A,13A,6D,14D,15A,16A,17A

Przypadek testowy 4

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

Wynik: 1A,1D,2D,3D,9A,10A,4D,4A,5D,6D,7D,8D,11A,12A,13A,15A,14D,15D,16A,17A,18D,19D,20A,21D,23A,22D,24A,25D,27A,28A,26D,29A,30A,31A

Powodzenia!

GolfScript, 154 znaków

:^,,{.^=46<{;-1}*)}%[.^n?)/zip[0]*]{1,%{,1>},}%:H"AD"1/]zip{~`{1$0=H{{0=}/}%.&$?)\+[\]}+/}%(2/\{0=)[\~\]}$+[]{1${1=1$&},.!{;1$1<}*1<:F~~@|@F-\1$}do;;]','*

Dane wejściowe należy podać na STDIN. Przykłady dają następujące wyniki (sprawdź online ):

1A,1D,2D,3D,4A,5A,6A,7A

1A,1D,2D,5A,4D,4A,3D,3A,7A,8A,6D,9A

1A,2D,3D,4D,5D,7A,8D,9A,10A,11A,11D,12A,13A,6D,14D,15A,16A,17A

1A,1D,2D,3D,9A,10A,4D,4A,5D,6D,7D,8D,11A,12A,13A,15A,14D,15D,16A,17A,18D,19D,20A,21D,23A,22D,24A,25D,27A,28A,26D,29A,30A,31A

Mathematica 806 477

(Wygląda na to, że wystąpiła usterka w porządku kroków rozwiązania. Patrzę na to.)

Grał w golfa

Funkcja qznajduje kolejność rozwiązań krzyżówek.

i = Dimensions; v = MemberQ; u = Position; y = ToString; k = Select;
q@t_ :=
 (g@p_ := Characters@StringSplit[p, "\n"];
  w = g@t;
  a[{r_, c_}, z_] := (c != i[z][[2]]) \[And] 
    v[u[z, "."], {r, c + 1}] \[And] ((c == 1) \[Or] 
      v[u[z, "#"], {r, c - 1}]);
  b@z_ := k[u[z, "."], a[#, z] &];
  d[{r_, c_}, z_] := (r != i[z][[2]]) \[And] 
    v[u[z, "."], {r + 1, c}] \[And] ((r == 1) \[Or] 
      v[u[z, "#"], {r - 1, c}]);
  e@z_ := k[u[z, "."], d[#, z] &];
  Cases[Flatten[{
       If[v[b[w], #[[1]]], y[#[[2]]] <> "A"],
       If[v[e[w], #[[1]]], y[#[[2]]] <> "D"]} & /@ (MapIndexed[List, 
        b[w] \[Union] e[w]] /. {{r_, c_}, {i_}} :> ({r, c} -> i))], 
   Except[Null]])

Nie golfił

q[t7_]:=
Module[{d,acrossSquareQ,acrossSquares,downSquareQ,downSquares,m,numberedCells},
(*w=g[t7];*)
g[p2_]:=Characters@StringSplit[p2,"\n"];
w=g[t7];
acrossSquareQ[{r_,c_},z_]:=(c!=Dimensions[z][[2]])\[And]MemberQ[Position[z,"."],{r,c+1}] \[And]((c==1)\[Or]MemberQ[Position[z,"#"],{r,c-1}]);
acrossSquares[z_]:=Select[Position[z,"."],acrossSquareQ[#,z]&];
downSquareQ[{r_,c_},z_]:=(r!=Dimensions[z][[2]])\[And]MemberQ[Position[z,"."],{r+1,c}] \[And]((r==1)\[Or]MemberQ[Position[z,"#"],{r-1,c}]);
downSquares[z_]:=Select[Position[z,"."],downSquareQ[#,z]&];
numberedCells[z_]:=acrossSquares[z]\[Union]downSquares[z];
m=MapIndexed[List,numberedCells[w]]/.{{r_?IntegerQ,c_?IntegerQ},{i_?IntegerQ}}:> ({r,c}-> i);
Cases[Flatten[{
If[MemberQ[acrossSquares[w],#[[1]]],ToString[#[[2]]]<>"A"],
If[MemberQ[downSquares[w],#[[1]]],ToString[#[[2]]]<>"D"]}&/@m],Except[Null]]]

boardwyświetla krzyżówkę. Kod nie jest uwzględniany w liczbie znaków. qWypożyczono tutaj kilka podfunkcji .

board[p_]:=
Module[{q,g,w,downSquareQ,downSquares,acrossSquareQ,acrossSquares,numberedCells,m},
downSquareQ[{r_,c_},z_]:=(r!=Dimensions[z][[2]])\[And]MemberQ[Position[z,"."],{r+1,c}] \[And]((r==1)\[Or]MemberQ[Position[z,"#"],{r-1,c}]);
downSquares[z_]:=Select[Position[z,"."],downSquareQ[#,z]&];
acrossSquareQ[{r_,c_},z_]:=(c!=Dimensions[z][[2]])\[And]MemberQ[Position[z,"."],{r,c+1}] \[And]((c==1)\[Or]MemberQ[Position[z,"#"],{r,c-1}]);
acrossSquares[z_]:=Select[Position[z,"."],acrossSquareQ[#,z]&];
numberedCells[z_]:=acrossSquares[z]\[Union]downSquares[z];
g[p2_]:=Characters@StringSplit[p2,"\n"];
w=g[p];
m=MapIndexed[List,numberedCells[w]]/.{{r_?IntegerQ,c_?IntegerQ},{i_?IntegerQ}}:> ({r,c}-> i);
Grid[ReplacePart[w,m],Dividers->All,Background->{None,None,(#-> Black)&/@Position[w,"#"]}]]

Przypadki testowe

1

t1=".....#
.#.#.#
...#..
.#.#.#
.....#
##.#..";
board[t1]
q[t1]

{„1A”, „1D”, „2D”, „3D”, „4A”, „5A”, „6A”, „7A”}

2)

t2=".....#..
.#.##..#
.#....#.
...##.#.
.####...
......##";

board[t2]
q[t2]

{„1A”, „1D”, „2D”, „3A”, „3D”, „4A”, „4D”, „5A”, „6D”, „7A”, „8A”, „9A”}

3)

t3=".........#
#.#.#.#.#.
....#...#.
#...#.#.#.
..###.#.#.
.#....#...
.#####...#
.....###..";

board[t3]

q[t3]

{„1A”, „2D”, „3D”, „4D”, „5D”, „6D”, „7A”, „8D”, „9A”, „10A”, „11A”, „11D”, „ 12A ”,„ 13A ”,„ 14D ”,„ 15A ”,„ 16A ”,„ 17A ”}

4

t4=".....#.........
.#.#.#.#.#.#.#.
...#...#.......
.#.#.#.#.#.#.#.
....#..........
##.#.#.#.#.#.#.
......#........
.###.#####.###.
........#......
.#.#.#.#.#.#.##
..........#....
.#.#.#.#.#.#.#.
.......#...#...
.#.#.#.#.#.#.#.
.........#.....";

board[t4]


q[t4]

{„1A”, „1D”, „2D”, „3D”, „4A”, „4D”, „5D”, „6D”, „7D”, „8D”, „9A”, „10A”, „ 11A ”,„ 12A ”,„ 13A ”,„ 14D ”,„ 15A ”,„ 15D ”,„ 16A ”,„ 17A ”,„ 18D ”,„ 19D ”,„ 20A ”,„ 21D ”,„ 22D ” , „23A”, „24A”, „25D”, „26D”, „27A”, „28A”, „29A”, „30A”, „31A”}