Nosaukums
Atrašanās vieta (vieta)
Laika limits
1.00s
Atmiņas limits
256.0 MB
Grūtība
33%

Definīcija

Lai cīnītos pret automašīnu zādzībām, speciālistu grupa ir izstrādājusi slepenas ierīces pirmo versiju. Ierīce tiek uzstādīta uz automašīnas un raida datus tikai par tās kustības virzienu.

Pilsētas karte ir taisnstūrveida rūtiņu laukums, kur katra rūtiņa atbilst vai nu vietai, kur drīkst braukt (tās kartē tiek apzīmētas ar '.'), vai arī vietai kur braukt nav iespējams (tās kartē tiek apzīmētas ar 'X'). Automašīnas sākotnējā atrašānās vieta kartē ir apzīmēta ar zvaigznīti ('*'). Automašīna var vairākkārt braukt cauri savai sākotnējai atrašanās vietai.

Automašīna katrā brīdī var braukt vienā no četriem virzieniem: uz ziemeļiem (uz augšu), uz dienvidiem (uz leju), uz austrumiem (pa labi), uz rietumiem (pa kreisi).

Automašīnas kustība tiek uzdota kā kustības virzienu virkne. Katrā no minētajiem virzieniem automašīna ir veikusi vismaz vienu rūtiņu.

Uzrakstiet programmu, kas dotai pilsētas kartei, automašīnas sākotnējās atrašanās vietai un kustības virzienu virknei atrod visas iespējamās tās atrašanās vietas kustības beigās!


Ievaddatu raksturojums

Ievaddatu pirmajā rindā dotas divu naturālu skaitļu R(pilsētas kartes rindu skaits, 1≤R≤50) un C(pilsētas kartes kolonu skaits, 1≤C≤50) vērtības, kas atdalītas ar tukšumsimbolu.

Katrā no nākošajām R faila rindām dots pa C simboliem ('.','X' vai '*') katrā. Faila i+1-ā rinda atbilst kartes i-tajai rindai.

Faila nākošajā rindā dota naturāla skaitļa N(kustības virzienu virknes garums, 1≤N≤1000) vērtība.

Katrā no nākošajām N faila rindām dots pa vienam vārdam katrā. Šis vārds var būt NORTH, SOUTH, WEST vai EAST, kas nozīmē, ka konkrētajā brīdī automašīna ir braukusi, attiecīgi, uz ziemeļiem, dienvidiem, rietumiem vai austrumiem. Virzieni ir doti tieši tādā secībā kā automašīna ir braukusi. Divi pēc kārtas doti virzieni savā starpā ir atšķirīgi! 


Izvaddatu raksturojums

Izvaddatiem jāsatur tieši R rindas pa C simboliem katrā. Tai jāatspoguļo pilsētas karte ar '*' tikai tajās vietās, kur kustības beigās var atrasties automobilis.


Piezīmes

Uzdevums izmantots Horvātijas informātikas olimpiādē 2001.gadā


Paraugdati

Stdin
3 4
....
*..X
X.X.
2
EAST
NORTH
Stdout
.**.
...X
X.X.

Stdin
4 5
.....
.X...
...*X
X.X..
3
NORTH
WEST
SOUTH
Stdout
.....
*X*..
*.*.X
X.X..

Stdin
10 9
........X
X..XX..X.
.X.XX.X..
...XX....
...XX....
.XXX..XX.
.......X.
..XXX.X..
X.X....X.
*.....X..
4
EAST
NORTH
EAST
SOUTH
Stdout
........X
X..XX.*X.
.X.XX.X..
...XX....
...XX.***
.XXX..XX*
.......X*
..XXX*X.*
X.X..*.X*
....**X.*

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.