C #, 600 574 bajtów
Kompletny program, przyjmuje dane wejściowe z STDIN, dane wyjściowe do STDOUT.
Edycja: wystąpił błąd w obsłudze zawijania (nie zepsuł się w żadnym z podanych przypadków testowych), który dodałby 1 bajt, więc zrobiłem trochę golfa, aby to zrekompensować.
using Q=System.Console;struct P{int p,d;static void Main(){string D="",L;int w=0,W=0,o,n=1;for(;(L=Q.ReadLine())!=null;D+=L)w=(o=(L+="X").Length+1)>w?o:w;for(;W<D.Length;)D=D.Insert(W+1,"".PadLeft(D[W++]>87?w-W%w:0));P[]K=new P[W*6];var T=new string[W*6];P c=K[o=0]=new P{p=D.IndexOf('S')};for(System.Action A=()=>{if(c.p>=0&c.p<W&System.Array.IndexOf(K,c)<0&&D[c.p]%8>0){T[n]=T[o]+L;K[n]=c;n=D[c.p]==69?-n:n+1;}};o<n;o++){c=K[o];L="R";c.d=++c.d%6;A();L="L";c.d=(c.d+4)%6;A();L="F";c=K[o];c.p+=new[]{~w,1-w,2,1+w,w-1,-2}[c.d%6];A();}Q.WriteLine(n>0?"Invalid maze!":T[-n]);}}
Zaczyna się od czytania na mapie, dołączania (do każdej linii, aby wiedział, gdzie się kończy, i może wrócić i dodać mnóstwo spacji, aby mapa była prostokątna, oraz z rzędem spacji po prawej stronie (oszczędza to wykonujemy kontrole pakowania, jak wyjaśnimy poniżej). W pewnym momencie oblicza szerokość prostokąta i określa całkowitą długość mapy.
Następnie inicjuje wszystko do pierwszego wyszukiwania szerokości. Tworzone są dwie duże tablice, jedna do przechowywania wszystkich stanów, które musimy zbadać w naszym wyszukiwaniu, druga do rejestrowania trasy, którą wybraliśmy się do każdego stanu. Stan początkowy jest dodawany do odpowiedniej tablicy, a wskaźniki głowy i ogona są wstępnie ustawione nieco powyżej. Wszystko ma indeks 1.
Następnie iterujemy, dopóki ogon nie uderzy w głowę, a przynajmniej wydaje się, że uderzył w głowę. Dla każdego stanu, który odwiedziliśmy, próbujemy dodać nowy stan w tym samym miejscu, w którym jesteśmy obracani w lewo lub w prawo, a następnie taki, w którym przesuwaliśmy się do przodu. Kierunki są indeksowane, a początkowy kierunek (domyślnie to 0) odpowiada „w górę w lewo”.
Gdy próbujemy stanić w kolejce stan, jest on sprawdzany, ale nie jest sprawdzany zawijaniem, ze względu na kolumny spacji po prawej stronie, które są odbierane przez „czy możemy tu być?” sprawdź (nie możesz przebywać na spacjach). Jeśli stan jest w kolejce, sprawdzamy, czy znajduje się on w Ekomórce, a jeśli tak, to ustawiamy, że głowa kolejki ma wartość minus sama, co powoduje zamknięcie głównej pętli i informuje ostatni wiersz programu, aby wydrukował poza odpowiednią trasę zamiast komunikatu o błędzie (który pokazuje, czy zabraknie stanów do rozwinięcia (ogon uderza w głowę).
using Q=System.Console;
// mod 8 table (the block of zeros is what we are after - it's everywhere we /can't/ go)
// 0 (space)
// O 0
// X 0
// S 3
// + 3
// E 5
struct P
{
int p,d;
static void Main()
{
// it's probably a bad thing that I have my own standards for naming this stupid read sequence by now
string D="", // map
L; // line/path char
int w=0, // width
W=0, // full length
o, // next state to expand
n=1; // next state to fill
for(;(L=Q.ReadLine())!=null;D+=L) // read in map
w=(o=(L+="X").Length+1)>w?o:w; // assertain max length (and mark end, and remove any need for wrap checking)
// now we need to add those trailing spaces...
for(;W<D.Length;)
D=D.Insert(W+1,"".PadLeft(D[W++]>87?w-W%w:0)); // inject a load of spaces if we hit an X
P[]K=new P[W*6]; // create space for due states (can't be more states than 6*number of cells)
var T=new string[W*6]; // create space for routes (never done it this way before, kind of exciting :D)
P c=K[o=0]=new P{p=D.IndexOf('S')}; // set first state (assignment to c is just to make the lambda shut up about unassigned variables)
// run bfs
for(
System.Action A=()=> // this adds c to the list of states to be expanded, if a whole load of checks pass
{
if(//n>0& // we havn't already finished - we don't need this, because we can't win on the first turn, so can't win unless we go forward, which we check last
c.p>=0&c.p<W& // c is within bounds
System.Array.IndexOf(K,c)<0&& // we havn't seen c yet (the && is to prevent the following lookup IOBing)
D[c.p]%8>0) // and we can move here (see table at top of code)
{
T[n]=T[o]+L; // store route
K[n]=c; // store state
n=D[c.p]==69?-n:n+1; // check if we are at the end, if so, set n to be negative of itself so we know, and can look up the route (otherwise, increment n)
}
}
;o<n;o++) // o<n also catches n<0
{
c=K[o]; // take current
L="R"; // say we are going right
c.d=++c.d%6; // turn right
A(); // go!
L="L"; // say we are going left
c.d=(c.d+4)%6; // turn left
A(); // go!
L="F"; // say we - you get the picture
c=K[o];
c.p+=new[]{~w,1-w,2,1+w,w-1,-2}[c.d%6]; // look up direction of travel (~w = -w-1)
A();
}
// check if we visited the end
Q.WriteLine(n>0?"Invalid maze!":T[-n]); // if n<0, then we found the end, so spit out the corresponding route, otherwise, the maze is invlida
}
}
Podobnie jak większość moich Wyszukiwań Grafów na tej stronie, dobrze wykorzystuję struktury C #, które domyślnie porównują dosłownie.
