// 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-tworzy pustą listę
//---------------------------------
queue::queue()
{
  head = tail = NULL;
}

// Destruktor-usuwa listę z pamięci
//-----------------------------------
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 = NULL;
  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 = NULL;
    delete p;
  }
}

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

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

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

  i = 0;            // Licznik wierszy
  do
  {
    cin >> s;       // Czytamy wiersz z wejścia
    if(s != "*")  // Jeśli nie jest to wiersz końcowy, to
    {
      if(n < i+1) // ustawiamy rozmiar tablicy
      {
        T = new string [i+10];
        for(j = 0; j < n; j++) T [j] = L [j];
        delete [] L;
        L = T;
        n = i+10;
      }
      L [i++] = s; // odczytany wiersz umieszczamy w tablicy M
    }
  } while(s != "*");

  n = i; // Liczba wierszy w L

  wst = kst = wwy = kwy = -1; // Współrzędne startu oraz wyjścia

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

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

  Q.push (wst); // W kolejce umieszczamy wierzchołek startowy
  Q.push (kst);

  while(!Q.empty())
  {
    w = Q.front(); Q.pop();  // Pobieramy z kolejki wiersz
    k = Q.front(); Q.pop();  // i kolumnę bieżącego wierzchołka

    // 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

            if(    i == -1) L [w+i][k+j] = 'd';  // z dołu
            else if(i ==  1) L [w+i][k+j] = 'g';  // z góry
            else if(j == -1) L [w+i][k+j] = 'p';  // z prawej
            else               L [w+i][k+j] = 'l';  // z lewej

            Q.push (w+i);  // Sąsiad zostaje umieszczony w kolejce
            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;
      }
    }
  }

  L [wwy][kwy] = 'W'; // Odtwarzamy znak wyjścia

  // 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 'g':
        case 'd':
        case 'p':
        case 'l': L [i][j] = ' ';
      }
    cout << L [i] << endl;
  }
  cout << endl;
}

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

int main()
{
  czytajL();    // Wczytujemy labirynt

  if((wst == -1) || (kst == -1) || (wwy == -1) || (kwy == -1))
    cout << "BRAK DEFINICJI S LUB W !!!\n";
  else
  {
    SzukajW(); // Szukamy wyjścia
    PiszL();   // Wyświetlamy wyniki poszukiwań
  }
  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-tworzy pustą listę
'---------------------------------
Constructor queue()
  head = 0
  tail = 0
End Constructor

' Destruktor-usuwa listę z pamięci
'-----------------------------------
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
'-----------------

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

' 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
  
  i = 0              ' Licznik wierszy
  Do
    Line Input #1;s  ' Czytamy wiersz z wejścia
    If s <> "*" Then ' Jeśli nie jest to wiersz końcowy, to
      If n < i Then  ' ustawiamy rozmiar tablicy
        ReDim Preserve L (i+10)
        n = i+10
      End If
      L (i) = s    ' odczytany wiersz umieszczamy w tablicy M
      i += 1
    End If
  Loop Until s = "*"

  Close #1
 
  n = i ' Liczba wierszy w L

  wst =-1: kst = -1: wwy = -1: kwy = -1 ' Współrzędne startu oraz wyjścia

  For i = 0 To n-1 ' Szukamy S i W
    For j = 1 To Len (L (i))
    	If Mid (L (i), j, 1) = "S" Then
        wst = i: kst = j  ' S znalezione
    	ElseIf Mid (L (i), j, 1) = "W" Then
        wwy = i: kwy = j  ' W znalezione
        Mid (L (i), j, 1) = "."
      End If
    Next
  Next
End Sub

' Procedura szukania wyjścia
'---------------------------
Sub SzukajW()
  Dim As queue Q
  Dim As Integer w, k ' Wiersz, kolumna bieżącego wierzchołka
  Dim As Integer i, j

  Q.push (wst) ' W kolejce umieszczamy wierzchołek startowy
  Q.push (kst)

  While Q.empty() = 0
  	
    w = Q.front(): Q.pop() ' Pobieramy z kolejki wiersz
    k = Q.front(): Q.pop() ' i kolumnę bieżącego wierzchołka

    ' 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
              Mid (L (w+i), k+j, 1) = "d"  ' z dołu
            ElseIf i =  1 Then
              Mid (L (w+i), k+j, 1) = "g"  ' z góry
            ElseIf j = -1 Then
              Mid (L (w+i), k+j, 1) = "p"  ' z prawej
            Else
              Mid (L (w+i), k+j, 1) = "l"  ' z lewej
            End If

            Q.push (w+i) ' Sąsiad zostaje umieszczony w kolejce
            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

  Mid (L (wwy), kwy, 1) = "W" ' Odtwarzamy znak wyjścia

  ' 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 ***
' **********************

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

End