OLIMPIADA NATIONALA DE INFORMATICA			SUCEAVA - 1996
CLASA A XI-A						26 martie

Problema BARIERE


   Un soricel se afla situat intr-un nod al unei retele dreptunghiulare de
dimensiune m x n, avand forma si numerotarea nodurilor conform figurii
de mai jos (in care m=4, n=3):

              1+-------2--------+3--------+4
              |         +         |         |
              |         |         |         |
              |         |         +         |
              5+-------+6---------7-------+8
              |         |         |         |
              |         |         |         |
              +         |         +         |
              9-------10+--------11------+12

  Fiecare nod V al retelei are EXACT o bariera pe o muchie VW, care blocheaza
trecerea soricelului de la V la W, DAR si de la W la V.

(Pentru exemplul din figura anterioara, in nodul 2 avem o bariera catre
nodul 6, care impiedica trecerea soricelului de la nodul 2 la nodul 6,
dar si de la nodul 6 la nodul 2.)

  Soricelul trebuie sa ajunga la o bucatica de cascaval, situata intr-un
alt nod al retelei, parcurgand reteaua pe drumul de cost minim, respectand
urmatoarele reguli:
  1. soricelul, aflat in nodul V, poate trece la nodul W, daca nu exista nici
o bariera pe muchia VW; aceasta trecere il costa 1 $.
  2. soricelul poate schimba pozitia barierei din nodul curent, ceea ce il
costa tot 1 $.

  (Pentru exemplul din figura anterioara, soricelul (presupus a fi initial
in nodul 2) poate ajunge in nodul 7, in mai multe moduri, de pilda:
   a) muta bariera din 2 (asezand-o catre nodul 1), se deplaseaza apoi n
nodul 6, apoi in 7 (costul: 3$);
   b) muta bariera din 2 (asezand-o catre nodul 1), se deplaseaza apoi n
nodul 6, apoi in nodul 10, unde pune bariera catre nodul 9, apoi se duce n
11, pune bariera de aici catre nodul 10 si, in sfarsit, se deplaseaza in
nodul 7 (costul: 7$)).

  Se cere sa se determine drumul de cost minim al soricelului catre cascaval.

  Un fisier de intrare are forma urmatoare:
  m n
  s c
  d11 d12 d13 ... d1m
  d21 d22 d23 ... d2m
  ...................
  dn1 dn2 dn3 ... dnm
unde: m si n sunt dimensiunile matricei
      s este nodul de unde pleaca soricelul
      c este nodul unde se afla cascavalul
      dij este pozitia initiala a barierei din nodul de pe linia i
      si coloana j, codificata prin unul din caracterele N,S,E,V, reprezentand
      punctul cardinal catre care este pusa bariera:

  Iesirea programului se realizeaza atat pe ecran, cat si intr-un fisier
text, scriindu-se varfurile drumului minim al soricelului, precum si costul
acestuia:
  v1 p1 v2 p2 ... vk pk
  cm

unde v1, v2, ..., vk sunt varfurile prin care trece soricelul,
                     inclusiv extremitatile;
     pi (1<=i<=k) este punctul cardinal in care se afla bariera din nodul vi,
        la parasirea acestuia;
     cm este costul minim al drumului.

Exemplu (pentru figura anterioara, m=4, n=3, s=1, c=7):

Intrare:

4 3
2 7
E S V V
E V N V
N E N V

Iesire:

2 E 6 V 7 N
3

Observatii:
  1. Datele sunt corecte.
  2. Daca exista mai multe solutii, se va afisa doar una.
  3. Daca nu exista drum, sa se scrie un mesaj corespunzator.
  4. m si n sunt numere intregi, 1<=m,n<=10.
  5. Nodul initial poate coincide cu nodul final.
  6. Punctele cardinale se considera astfel:
                         N
                        V E
                         S

Punctaj: 66,666666666666666666666666666666666666666666666666(6)

