// Znajdowanie wyjścia z labiryntu
// Data: 25.08.2013
// (C)2013 mgr Jerzy Wałaszek
//--------------------------------

program labirynt;

// Typy dla kolejki
type
  PSLel = ^SLel;
  SLel  =  record
    next : PSLel;
    v    : integer;
  end;

// Definicja typu obiektowego Queue
//---------------------------------
  Queue = object
    private
      head : PSLel;
      tail : PSLel;

    public
      constructor init;
      destructor destroy;
      function empty : boolean;
      function front : integer;
      procedure push(v : integer);
      procedure pop;
  end;

//---------------------
// Metody obiektu queue
//---------------------

// Konstruktor
//------------
constructor Queue.init;
begin
  head := nil;
  tail := nil;
end;

// Destruktor
//-----------
destructor Queue.destroy;
begin
  while not empty do
    pop;
end;

// Sprawdza,
// czy kolejka jest pusta
//-----------------------
function Queue.empty : boolean;
begin
  if head = nil then
    empty := true
  else
    empty := false;
end;

// Zwraca początek kolejki.
// Wartość specjalna to -MAXINT
//-----------------------------
function Queue.front : integer;
begin
  if head = nil then
    front := -MAXINT
  else
    front := head^.v;
end;

// Zapisuje do kolejki
//--------------------
procedure Queue.push(v : integer);
var
  p : PSLel;
begin
  new(p);
  p^.next := nil;
  p^.v := v;
  if tail = nil then
    head := p
  else
    tail^.next := p;
  tail := p;
end;

// Usuwa z kolejki
//----------------
procedure Queue.pop;
var
  p : PSLel;
begin
  if head <> nil then
  begin
    p := head;
    head := head^.next;
    if head = nil then
      tail := nil;
    dispose(p);
  end;
end;

// Zmienne globalne
//-----------------

var
  // Współrzędne startowe:
  // wiersz, kolumna
  ws, ks : integer;
  // Współrzędne wyjścia:
  // wiersz, kolumna
  ww, kw : integer;
  // Labirynt
  L : array of string;

// Odczytuje labirynt
// Wyszukuje wierzchołki
// startowy i wyjściowy
//----------------------
procedure czytajL;
var
  s : string;
  i, j : integer;
begin
  // Licznik wierszy
  i := 0;
  repeat
    // Czytamy wiersz z wejścia
    readln(s);
    // Jeśli nie jest to
    // wiersz końcowy, to
    if s <> '*' then
    begin
      // rozmiar tablicy
      if Length(L) < i+1 then
        SetLength(L, i+1);
      // odczytany wiersz
      // umieszczamy w tablicy L
      L[i] := s;
      // zwiększamy licznik wierszy
      inc(i);
    end;
  until s = '*';
  // Ustawiamy wstępnie
  // współrzędne startu
  ws := -1; ks := -1;
  // oraz wyjścia
  ww := -1; kw := -1;
  // Szukamy S i W
  for i := 0 to High(L) do
    for j := 1 to Length(L[i]) do
      if L[i][j] = 'S' then
      begin
        // S znalezione
        ws := i; ks := j;
      end
      else if L[i][j] = 'W' then
      begin
        // W znalezione
        ww := i; kw := j;
        L[i][j] := '.';
      end;
end;

// Procedura szukania wyjścia
//---------------------------
procedure SzukajW;
var
  // Kolejka
  Q : Queue;
  // Wiersz, kolumna
  // bieżącego wierzchołka
  w, k : integer;
  i, j : integer;

begin
  // Inicjujemy kolejkę
  Q.init;
  // W kolejce umieszczamy
  // wierzchołek startowy
  Q.push(ws);
  Q.push(ks);
  while Q.empty = false do
  begin
    // Pobieramy z kolejki
    // wiersz
    w := Q.front; Q.pop;
    // i kolumnę bieżącego
    // wierzchołka
    k := Q.front; Q.pop;
    // Sprawdzamy, czy
    // osiągnęliśmy wyjście
    if (w = ww) and (k = kw) then
      break;
    // Przeglądamy sąsiadów
    // bieżącego wierzchołka
    for i := -1 to 1 do
      for j := -1 to 1 do
        if (i <> j) and
           ((i = 0) or (j = 0)) then
        begin
          if L[w+i][k+j] = '.' then
          begin
            // W komórce sąsiada
            // zapisujemy, skąd
            // przyszliśmy do niej
            if i = -1 then
              // z dołu
              L[w+i][k+j] := 'd'
            else if i =  1 then
              // z góry
              L[w+i][k+j] := 'g'
            else if j = -1 then
              // z prawej
              L[w+i][k+j] := 'p'
            else
              // z lewej
              L[w+i][k+j] := 'l';
            // Sąsiad zostaje
            // umieszczony w kolejce
            Q.push(w+i);
            Q.push(k+j);
          end;
        end;
  end;
  // Czyścimy kolejkę
  Q.destroy;
end;

// Procedura wypisuje labirynt
// z ewentualną ścieżką
// Zastępuje znaki kierunków
// znakiem +
//----------------------------
procedure PiszL;
var
  i, j : integer;
  c   : char;
begin
  // Najpierw sprawdzamy,
  // czy ścieżka została
  // znaleziona. Jeśli tak,
  // to zastępujemy ją znakami +
  if L[ww][kw] <> '.' then
  begin
    i := ww; j := kw;
    while (i <> ws) or
          (j <> ks) do
    begin
      c := L[i][j];
      L[i][j] := '+';
      case c of
        'd' : inc(i);
        'g' : dec(i);
        'p' : inc(j);
        'l' : dec(j);
      end;
    end;
  end;
  // Odtwarzamy znak wyjścia
  L[ww][kw] := 'W';
  // Teraz usuwamy znaki kierunku
  // i wypisujemy labirynt
  for i := 0 to High(L) do
  begin
    for j := 1 to Length(L[i]) do
      case L[i][j] of
        'g',
        'd',
        'p',
        'l' : L[i][j] := ' ';
      end;
    writeln(L[i]);
  end;
  writeln;
end;

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

begin
  // Wczytujemy labirynt
  czytajL;
  if (ws = -1) or
     (ks = -1) or
     (ww = -1) or
     (kw = -1) then
    writeln('BRAK DEFINICJI S LUB W !!!')
  else
  begin
    // Szukamy wyjścia
    SzukajW;
    // Wyświetlamy wyniki poszukiwań
    PiszL;
  end;
end.

// Znajdowanie wyjścia z labiryntu
// Data: 25.08.2013
// (C)2013 mgr Jerzy Wałaszek
//--------------------------------

#include <iostream>
#include <string>

using namespace std;

const int MAXINT = 2147483647;

// Typy dla kolejki
struct SLel
{
  SLel * next;
  int v;
};

// Definicja typu
// obiektowego Queue
//------------------
class Queue
{
  private:
    SLel * head;
    SLel * tail;

  public:
    Queue(); // konstruktor
    ~Queue(); // destruktor
    bool empty(void);
    int  front(void);
    void push(int v);
    void pop(void);
};

//---------------------
// Metody obiektu Queue
//---------------------

// Konstruktor
//------------
Queue::Queue()
{
  head = tail = NULL;
}

// Destruktor
//-----------
Queue::~Queue()
{
  while(head) pop();
}

// Sprawdza,
// czy kolejka jest pusta
//-----------------------
bool Queue::empty(void)
{
  return !head;
}

// Zwraca początek kolejki.
// Wartość specjalna to -MAXINT
//-----------------------------
int Queue::front(void)
{
  if(head) return head->v;
  else     return -MAXINT;
}

// Zapisuje do kolejki
//--------------------
void Queue::push(int v)
{
  SLel * p = new SLel;
  p->next = nullptr;
  p->v = v;
  if(tail) tail->next = p;
  else     head = p;
  tail = p;
}

// Usuwa z kolejki
//----------------
void Queue::pop(void)
{
  if(head)
  {
    SLel * p = head;
    head = head->next;
    if(!head) tail = nullptr;
    delete p;
  }
}

// Zmienne globalne
//-----------------

// Współrzędne startowe:
// wiersz, kolumna
int wst, kst;
// Współrzędne wyjścia:
// wiersz, kolumna
int wwy, kwy;
// Liczba wierszy
int n = 10;
// Labirynt
string * L = new string [n];

// Odczytuje labirynt
// Wyszukuje wierzchołki
// startowy i wyjściowy
//----------------------
void czytajL()
{
  string s, * T;
  int i, j;

  // Licznik wierszy
  i = 0;
  do
  {
    // Czytamy wiersz z wejścia
    cin >> s;
    // Jeśli nie jest to
    // wiersz końcowy, to
    if(s != "*")
    {
      // ustawiamy rozmiar
      // tablicy
      if(n < i+1)
      {
        T = new string [i+10];
        for(j = 0; j < n; j++)
          T[j] = L[j];
        delete [] L;
        L = T;
        n = i+10;
      }
      // odczytany wiersz
      // umieszczamy w tablicy L
      L[i++] = s;
    }
  } while(s != "*");
  // Liczba wierszy w L
  n = i;
  // Współrzędne startu oraz wyjścia
  wst = kst = wwy = kwy = -1;

  // Szukamy S i W
  for(i = 0; i < n; i++)
    for(j = 0;
        j < (int)L[i].length();
        j++)
      if(L[i][j] == 'S')
      {
        // S znalezione
        wst = i; kst = j;
      }
      else if(L[i][j] == 'W')
      {
        // W znalezione
        wwy = i; kwy = j;
        L[i][j] = '.';
      }
}

// Procedura szukania wyjścia
//---------------------------
void SzukajW()
{
  Queue Q;
  // Wiersz, kolumna
  // bieżącego wierzchołka
  int w, k;
  int i, j;

  // W kolejce umieszczamy
  // wierzchołek startowy
  Q.push(wst);
  Q.push(kst);
  while(!Q.empty())
  {
    // Pobieramy z kolejki
    // wiersz
    w = Q.front(); Q.pop();
    // i kolumnę bieżącego
    // wierzchołka
    k = Q.front(); Q.pop();
    // Sprawdzamy, czy
    // osiągnęliśmy wyjście
    if((w == wwy) && (k == kwy))
      break;
    // Przeglądamy sąsiadów
    // bieżącego wierzchołka
    for(i = -1; i <= 1; i++)
      for(j = -1; j <= 1; j++)
        if((i != j) && (!i || !j))
        {
          if(L[w+i][k+j] == '.')
          {
            // W komórce sąsiada
            // zapisujemy, skąd
            // przyszliśmy do niej
            // z dołu
            if(i == -1)
              L[w+i][k+j] = 'd';
            // z góry
            else if(i ==  1)
              L[w+i][k+j] = 'g';
            // z prawej
            else if(j == -1)
              L[w+i][k+j] = 'p';
            // z lewej
            else
              L[w+i][k+j] = 'l';
             // Sąsiad zostaje
             // umieszczony w kolejce
            Q.push(w+i);
            Q.push(k+j);
          }
        }
  }
}

// Procedura wypisuje labirynt
// z ewentualną ścieżką. Zastępuje
// znaki kierunków znakiem +
//--------------------------------
void PiszL()
{
  int i, j;
  char c;

  // Najpierw sprawdzamy,
  // czy ścieżka została
  // znaleziona. Jeśli tak,
  // to zastępujemy ją znakami +
  if(L[wwy][kwy] != '.')
  {
    i = wwy; j = kwy;
    while((i != wst) || (j != kst))
    {
      c = L[i][j];
      L[i][j] = '+';
      switch(c)
      {
        case 'd' : i++; break;
        case 'g' : i--; break;
        case 'p' : j++; break;
        case 'l' : j--; break;
      }
    }
  }
  // Odtwarzamy znak wyjścia
  L[wwy][kwy] = 'W';
  // Teraz usuwamy znaki kierunku
  // i wypisujemy labirynt
  for(i = 0; i < n; i++)
  {
    for(j = 0;
        j < (int)L[i].length();
        j++)
      switch(L[i][j])
      {
        case '.':
        case 'g':
        case 'd':
        case 'p':
        case 'l': L[i][j] = ' ';
      }
    cout << L[i] << endl;
  }
  cout << endl;
}

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

int main()
{
  // Wczytujemy labirynt
  czytajL();
  if((wst == -1) ||
     (kst == -1) ||
     (wwy == -1) ||
     (kwy == -1))
    cout << "BRAK DEFINICJI S LUB W !!!"
         << endl;
  else
  {
    // Szukamy wyjścia
    SzukajW();
    // Wyświetlamy wyniki
    // poszukiwań
    PiszL();
  }
  return 0;
}

' Znajdowanie wyjścia z labiryntu
' Data: 25.08.2013
' (C)2013 mgr Jerzy Wałaszek
'--------------------------------

Const MAXINT = 2147483647

' Typy dla kolejki
Type SLel
  next As SLel Ptr
  v As Integer
End Type

' Definicja typu obiektowego Queue
'---------------------------------
Type Queue
  Private:
    head As SLel Ptr
    tail As SLel Ptr

  Public:
    Declare Constructor
    Declare Destructor
    Declare Function empty As Integer
    Declare Function front As Integer
    Declare Sub push(ByVal v As Integer)
    Declare Sub pop
End Type

'---------------------
' Metody obiektu Queue
'---------------------

' Konstruktor
'------------
Constructor Queue
  head = 0
  tail = 0
End Constructor

' Destruktor
'-----------
Destructor Queue
  While empty = 0: pop: Wend
End Destructor

' Sprawdza, czy kolejka jest pusta
'---------------------------------
Function Queue.empty As Integer
  If head = 0 Then Return 1
  Return 0
End Function

' Zwraca początek kolejki.
' Wartość specjalna to -MAXINT
'-----------------------------
Function Queue.front As Integer
  If head = 0 then
    front = -MAXINT
  Else
    front = head->v
  End If
End Function

' Zapisuje do kolejki
'--------------------
Sub Queue.push(ByVal v As Integer)
  Dim p As SLel Ptr
  p = new SLel
  p->next = 0
  p->v = v
  If tail = 0 Then
    head = p
  Else
    tail->next = p
  End If
  tail = p
End Sub

' Usuwa z kolejki
'----------------
Sub Queue.pop
  Dim p As SLel Ptr
  If head Then
    p = head
    head = head->next
    If head = 0 Then tail = 0
    Delete p
  End If
End Sub

' Zmienne globalne
'-----------------
' Współrzędne startowe-wiersz, kolumna
Dim Shared As Integer wst, kst
' Współrzędne wyjścia -wiersz, kolumna
Dim Shared As Integer wwy, kwy
' Liczba wierszy
Dim Shared As Integer n = 10
' Labirynt
Dim Shared As String L(n)

' Odczytuje labirynt
' Wyszukuje wierzchołki
' startowy i wyjściowy
'----------------------
Sub CzytajL
  Dim As String s
  Dim As Integer i, j

  Open Cons For Input As #1
  ' Licznik wierszy
  i = 0
  Do
    ' Czytamy wiersz z wejścia
    Line Input #1; s
    ' Jeśli nie jest to wiersz końcowy, to
    If s <> "*" Then
      ' ustawiamy rozmiar tablicy
      If n < i Then
        ReDim Preserve L(i+10)
        n = i+10
      End If
      ' odczytany wiersz umieszczamy
      ' w tablicy L
      L(i) = s
      i += 1
    End If
  Loop Until s = "*"
  Close #1
  ' Liczba wierszy w L
  n = i
  ' Współrzędne startu oraz wyjścia
  wst =-1: kst = -1: wwy = -1: kwy = -1
  ' Szukamy S i W
  For i = 0 To n-1
    For j = 1 To Len(L(i))
      If Mid(L(i), j, 1) = "S" Then
        ' S znalezione
         wst = i: kst = j
      ElseIf Mid(L(i), j, 1) = "W" Then
        ' W znalezione
        wwy = i: kwy = j
        Mid(L(i),j,1) = "."
      End If
    Next
  Next
End Sub

' Procedura szukania wyjścia
'---------------------------
Sub SzukajW
  Dim As Queue Q
  ' Wiersz, kolumna bieżącego wierzchołka
  Dim As Integer w, k
  Dim As Integer i, j
  ' W kolejce umieszczamy
  ' wierzchołek startowy
  Q.push(wst)
  Q.push(kst)
  While Q.empty = 0
    ' Pobieramy z kolejki wiersz
    w = Q.front: Q.pop
    ' i kolumnę bieżącego wierzchołka
    k = Q.front: Q.pop
    ' Sprawdzamy, czy osiągnęliśmy wyjście
    If (w = wwy) AndAlso _
       (k = kwy) Then Exit While
    ' Przeglądamy sąsiadów
    ' bieżącego wierzchołka
    For i = -1 To  1
      For j = -1 To 1
        If (i <> j) AndAlso _
           ((i = 0) OrElse (j = 0)) Then
          If Mid(L(w+i), k+j, 1) = "." Then
            ' W komórce sąsiada zapisujemy,
            ' skąd przyszliśmy do niej
            If i = -1 Then
              ' z dołu
              Mid(L(w+i), k+j, 1) = "d" 
            ElseIf i =  1 Then
              ' z góry
              Mid(L(w+i), k+j, 1) = "g"
            ElseIf j = -1 Then
              ' z prawej
              Mid(L(w+i), k+j, 1) = "p"
            Else
              ' z lewej
              Mid(L(w+i), k+j, 1) = "l"
            End If
            ' Sąsiad zostaje
            ' umieszczony w kolejce
            Q.push(w+i)
            Q.push(k+j)
          End if
        End If
      Next
    Next
  Wend
End Sub

' Procedura wypisuje labirynt
' z ewentualną ścieżką
' Zastępuje znaki kierunków znakiem -.
'-------------------------------------
Sub PiszL
  Dim As Integer i, j
  Dim As String * 1 c

  ' Najpierw sprawdzamy, czy ścieżka
  ' została znaleziona. Jeśli tak, to
  ' zastępujemy ją znakami +
  If Mid(L(wwy), kwy, 1) <> "." Then
    i = wwy: j = kwy
    while(i <> wst) OrElse (j <> kst)
      c = Mid(L(i), j, 1)
      Mid(L(i), j, 1) = "+"
      Select Case c
      	Case "d"
          i += 1
      	Case "g"
          i -= 1
      	Case "p"
          j += 1
      	Case "l"
          j -= 1
      End Select
    Wend
  End If
  ' Odtwarzamy znak wyjścia
  Mid(L(wwy), kwy, 1) = "W"
  ' Teraz usuwamy znaki kierunku
  ' i wypisujemy labirynt
  For i = 0 To n-1
    For j = 0 To Len(L(i))
      Select Case Mid(L(i), j, 1)
        Case "g", "d", "p", "l"
          Mid(L(i), j, 1) = " "
      End Select
    Next
    Print L(i)
  Next
  Print
End Sub

' **********************
' *** PROGRAM GŁÓWNY ***
' **********************

' Wczytujemy labirynt
CzytajL
Print
If (wst = -1) OrElse _
   (kst = -1) OrElse _
   (wwy = -1) OrElse _
   (kwy = -1) Then
  Print "BRAK DEFINICJI S LUB W !!!"
Else
  ' Szukamy wyjścia
  SzukajW
  ' Wyświetlamy wyniki poszukiwań
  PiszL
End If
End

# Znajdowanie wyjścia z labiryntu
# Data: 26.12.2024
# (C)2024 mgr Jerzy Wałaszek
#--------------------------------

MAXINT = 2147483647

# Klasa elementu kolejki
class SLel:
    def __init__(self):
        self.next = None
        self.v = 0


# Klasa Queue
#------------
class Queue:
    # Konstruktor
    def __init__(self):
        self.head = None
        self.tail = None


    # Destruktor
    def __del__(self):
        while not self.empty():
            self.pop()


    # Sprawdza, czy kolejka jest pusta
    def empty(self):
        if not self.head: return True
        return False


    # Zwraca początek kolejki.
    # Wartość specjalna to -MAXINT
    def front(self):
        global MAXINT
        if not self.head:
            return -MAXINT
        else:
            return self.head.v


    # Zapisuje do kolejki
    def push(self, v):
        p = SLel()
        p.next = 0
        p.v = v
        if not self.tail:
            self.head = p
        else:
            self.tail.next = p
        self.tail = p


    # Usuwa z kolejki
    def pop(self):
        if self.head:
            self.head = self.head.next
            if not self.head:
                self.tail = None


# Zmienne globalne

# Liczba wierszy
n = 10
# Labirynt
lab = [""] * n

# Odczytuje labirynt
# Wyszukuje wierzchołki
# startowy i wyjściowy
def czytaj_lab():
    global n,wst,kst,wwy,kwy,lab
    s = ""
    # Licznik wierszy
    i = 0
    while s != "*":
        # Czytamy wiersz z wejścia
        s = input()
        # Jeśli nie jest to wiersz końcowy, to
        if s != "*":
            # ustawiamy rozmiar tablicy
            while n <= i:
                n += 1
                lab.append("")
            # odczytany wiersz umieszczamy
            # w tablicy lab
            lab[i] = s
            i += 1
    n = i
    # Współrzędne startu oraz wyjścia
    wst =-1
    st = -1
    wwy = -1
    kwy = -1
    # Szukamy S i W
    for i in range(n):
        for j in range(len(lab[i])):
            if lab[i][j] == "S":
                # S znalezione
                wst = i
                kst = j
            elif lab[i][j] == "W":
                # W znalezione
                wwy = i
                kwy = j
                lab[i] = lab[i][:j]+"."+lab[i][j+1:]


# Procedura szukania wyjścia
#---------------------------
def szukaj_w():
    global lab,wst,kst,wwy,kwy
    q = Queue()
    # W kolejce umieszczamy
    # wierzchołek startowy
    q.push(wst)
    q.push(kst)
    while not q.empty():
        # Pobieramy z kolejki wiersz
        w = q.front()
        q.pop()
        # i kolumnę bieżącego wierzchołka
        k = q.front()
        q.pop()
        # Sprawdzamy, czy osiągnęliśmy wyjście
        if (w == wwy) and (k == kwy): break
        # Przeglądamy sąsiadów
        # bieżącego wierzchołka
        for i in range(-1,2):
            for j in range(-1,2):
                if (i != j) and ((i == 0) or (j == 0)):
                    if lab[w+i][k+j] == ".":
                        # W komórce sąsiada zapisujemy,
                        # skąd przyszliśmy do niej
                        if i == -1:
                            # z dołu
                            lab[w+i] = lab[w+i][:k+j]+"d"+ \
                                       lab[w+i][k+j+1:]
                        elif i == 1:
                            # z góry
                            lab[w+i] = lab[w+i][:k+j]+"g"+ \
                                       lab[w+i][k+j+1:]
                        elif j == -1:
                            # z prawej
                            lab[w+i] = lab[w+i][:k+j]+"p"+ \
                                       lab[w+i][k+j+1:]
                        else:
                            # z lewej
                            lab[w+i] = lab[w+i][:k+j]+"l"+ \
                                       lab[w+i][k+j+1:]
                        # Sąsiad zostaje
                        # umieszczony w kolejce
                        q.push(w+i)
                        q.push(k+j)


# Procedura wypisuje labirynt
# z ewentualną ścieżką
# Zastępuje znaki kierunków znakiem -.
#-------------------------------------
def pisz_lab():
    global lab,wst,kst,wwy,kwy

    # Najpierw sprawdzamy, czy ścieżka
    # została znaleziona. Jeśli tak, to
    # zastępujemy ją znakami +
    if lab[wwy][kwy] != ".":
        i = wwy
        j = kwy
        while (i != wst) or (j != kst):
            c = lab[i][j]
            lab[i] = lab[i][:j] + "+" + lab[i][j+1:]
            match c:
                case "d":
                    i += 1
                case "g":
                    i -= 1
                case "p":
                    j += 1
                case "l":
                    j -= 1
    # Odtwarzamy znak wyjścia
    lab[wwy] = lab[wwy][:kwy] + "W" + lab[wwy][kwy+1:]
    # Teraz usuwamy znaki kierunku
    # i wypisujemy labirynt
    for i in range(n):
        for j in range(len(lab[i])):
            match lab[i][j]:
                case "g"|"d"|"p"|"l":
                    lab[i] = lab[i][:j]+" "+lab[i][j+1:]
        print(lab[i])
    print()


# **********************
# *** PROGRAM GŁÓWNY ***
# **********************

wst,kst,wwy,kwy = -1,-1,-1,-1
# Wczytujemy labirynt
czytaj_lab()
print()
if (wst == -1) or \
   (kst == -1) or \
   (wwy == -1) or \
   (kwy == -1):
    print("BRAK DEFINICJI S LUB W !!!")
else:
    # Szukamy wyjścia
    szukaj_w()
    # Wyświetlamy wyniki poszukiwań
    pisz_lab()