MELACAK MOBIL HILANG

 

Di suatu kota, seorang pencuri mobil diduga telah mencuri mobil Prof Linglung lalu mengendarainya ke suatu tempat di kota itu juga. Sang Pencuri tidak menyadari ternyata Prof Linglung telah suatu memasang alat pengaman dalam mobil itu yang selalu memancarkan informasi tertentu mengenai mobil tersebut saat mobil itu bergerak.

Sayangnya alat tersebut bukan sejenis alat modern yang dapat memancarkan informasi koodinat keberadaannya, melainkan suatu alat yang hanya mendeteksi ke arah mana mobil itu menghadap menurut empat arah mata angin: utara, selatan, barat, dan timur, dan memancarkannya. Alat hanya memancarkan satu kali saja sebelum terjadi terjadi perubahan berikutnya.

Kebetulan jalan-jalan di kota itu selalu vertikal atau horisontal dengan simpangan-simpangan pada posisi bilangan bulat. Data yang terekam terakhir oleh Prof Lingkung dari mobil itu adalah posisi mobil diparkir terakhir sebelum hilang (kita sebut pada posisis awal), kemudian sejak itu terekam sederetan sinyal-sinyal arah hadap mobil tersebut hingga kemudian berhenti entah di mana. Prof Linglung kaget sehingga ia menjadi benar-benar linglung karena rupanya mobil itu menyimpan banyak kenangan baginya.

Tuliskan suatu program dengan nama LACAK.PAS untuk membantu si profesor guna melacak mobil tersebut menggunakan peta jalan-jalan di kota tersebut, posisi awal serta sederetan data arah hadap dari mobil ketika ia bergerak. Program harus dapat menemukan semua kemungkinan mobil berada saat ini.

Peta dari kota tersebut berupa matriks yang berisikan bagian jalan (dapat dilalui kendaraan) dan bagian yang tidak dapat dilalui kendaraan (misalnya bangunan, sungai, dsb). Pada setiap koordinat bilangan bulatnya (elemen matriks) tanda titik (‘.’) menyatakan bagian yang dapat dilalui mobil, tanda ‘X’ menyatakan bagian yang tidak dapat dilalui mobil. Posisi awal mobil adalah bagian yang dapat dilalui tapi ditandai dengan karakter ‘*’ (tentu suatu mobil dapat melalui kembali posisi awal ini).

Pada setiap arah gerakan dipastikan alat pada mobil akan memancarkan sinyal tepat satu kali (mungkin pemicu alat untuk mengirimkan sinyal ada pada sistem setir mobil). Juga pada suatu arah dipastikan mobil bergerak melalui satu atau lebih titik koordinat peta.

 

Format Masukan

Masukan adalah file teks bernama LACAK.IN yang berisi data dalam format sebagai berikut.

·        Baris pertama dari file masukan berisi dua bilangan integer R dan C, 1 ≤ R ≤ 50, 1 ≤ C ≤ 50, yang dipisahkan oleh suatu karakter spasi, masing-masing menyatakan baris dan kolom dari peta kota tersebut.

·        Pada setiap dari R baris berikutnya terdapat deretan C buah karakter: ‘X’, ‘.’ atau ‘*’ yang menjelaskan bagian-bagian dari peta seperti pada penjelasan di atas.

·        Setelah itu, pada baris ke (R+2) tedapat bilangan integer N, 1 ≤ N ≤ 1000, yang menyatakan banyaknya sinyal arah mobil yang terekam.

·        Masing-masing dari N baris berikutnya berisi string-string NORTH, SOUTH, WEST dan EAST, yang menyatakan arah gerakan mobil.

·        Tidak ada dua sinyal berurutan yang sama.

 

Format Keluaran

Keluaran adalah file teks dengan nama LACAK.OUT. Keluaran berisi peta dari kota tersebut dalam R baris sebagaimana dalam file masukan, namun dengan sejumlah krakter ‘*’ yang menandai kemungkinan mobil itu berhenti. Jika titik semula bertanda ‘*’ dan akhirnya tidak bertanda ‘*’ haruslah menjadi bertanda ‘.’.

 

Contoh

LACAK.IN

 

3 4

....

*..X

X.X.

2

EAST

NORTH

 

LACAK.OUT

 

.**.

...X

X.X.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

LACAK.IN

 

4 5

.....

.X...

...*X

X.X..

3

NORTH

WEST

SOUTH

 

LACAK.OUT

 

.....

*X*..

*.*.X

X.X..

 

 

 

 

 

 

 

 

 

 

 

 

 

LACAK.IN

 

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

 

LACAK.OUT

 

........X

X..XX.*X.

.X.XX.X..

...XX....

...XX.***

.XXX..XX*

.......X*

..XXX*X.*

X.X..*.X*

....**X.*