Pembahasan Soal Lacak

Soal ini merupakan graph traversal BFS (Breadth Firsh Search) Khusus untuk masalah ini BFS dapat diimplementasikan tanpa menggunakan queue untuk menyimpan pencabangannya (breadthnya).

Idenya, dari suatu titik dan arah, kita mendapatkan sejumlah titik berikutnya sebagai breadth dalam BFS. Karena ukuran matrix 50x50 maka untuk kasus terburuk akan ada 49x49=2401 titik dalam breadth. Karena searching space sangat terbatas maka breadth tidak akan mengalami "peledakan".

Jadi kita menggunakan array breadth yang setiap elemennya menyimpan koordinat titik pencabangan. Dalam inisialisasi array hanya berisi satu titik yaitu posisi awal mobil.

Dalam setiap sinyal arah yang dibaca maka dari setiap titik dalam array breadth ini kita temukan kembali semua kemungkinan titik berikutnya di dalam peta dan menandainya. Setelah hal tersebut dilakukan untuk semua titik dalam breadth maka titik-titik pada peta yang telah ditandai dicatat ke dalam array breadth.

Hal tersebut dilakukan untuk setiap masukah yang dibaca dan setelah masukan arah terakhir maka tanda-tanda pada peta menyatakan semupa kemungkinan posisi mobil terakhir.

Dalam implementasinya kita perlu definisikan type posisi berikut.

type 
    posisi = record r, c: integer end;

Breadth adalah array dari elemen bertype posisi ini.

Selanjutnya kita perlu prosedur untuk memindahkan posisi bertanda "*" ke dalam array breadth.

    nb := 0;
    for i := 1 to nrow do
        for j := 1 to ncol do
            if peta[i,j] = '*' then begin
                inc(nb);
                breadth[nb].r := i; 
                breadth[nb].c := j;
                peta[i,j] := '.'; { clearkan posisi tsb}
            end;

Lalu untuk setiap titik breadth[b] dilakukan penandaan kembali posisi selanjutnya sesuai dengan arah yang diberikan. Misalnya untuk arah EAST maka

posNext := breadth[b];
inc(posNext.c);
while Jalan(posNext) do begin
    peta[posNext.r,posNext.c] := '*';
    inc(posNext.c);
end;

Untuk arah NORTH maka lakukan dengan

posNext := breadth[b];
dec(posNext.r);
while Jalan(posNext) do begin
    peta[posNext.r,posNext.c] := '*';
    dec(posNext.r);
end;

Untuk arah-arah lain diserahkan pada anda untuk melengkapi. Juga anda seharusnya dapat membuat fungsi Jalan(posNext) untuk memeriksa apakah pada posisi tersebut adalah jalan atau bukan.

function Jalan(posNext: posisi): boolean;
begin
    ....
    { kalau keluar peta maka false }
    { kalau tembok maka false }
    { kalau tidak maka true }
    ....
end;

Setelah semua titik pada breadth diproses maka breadh dikosongkan kembali dan diisi oleh titik-titik pada peta yang bertanda "*" kembali (dengan memanggil procedure di paling atas).

Setelah arah masukan terakhir maka peta langsung dituliskan sebagai keluaran.gampang khan???

Sebagai contoh, perhatikan peta masukan berikut ini

..........
.X.X..XXX.
.X..X.....
.X..X.....
....X.....
*......XX.
..........

breadth hanya berisi 1 titik, yaitu (6.1). Jika kemudian masukan arah adalah EAST maka breadth kemudian akan berisi titik-titik di samping kanan tanda bintang yaitu posisi-posisi kosong sampai ketemu tembok. Sekarang peta menjadi sbb.

..........
.X.X..XXX.
.X..X.....
.X..X.....
....X.....
.******XX.
..........

breadth hanya berisi 6 titik, yaitu (6.2), (6,3),...,(6,7). Jika kemudian masukan adalah NORTH maka hal seperti di atas dilakukan ke arah atas untuk masing-masing tanda bintang. Dan peta menjadi sbb.

..*..*....
.X*X.*XXX.
.X**X**...
.X**X**...
.***X**...
.......XX.
..........

Jika kemudian masukan adalah WEST maka hal seperti di atas dilakukan ke arah atas untuk masing-masing tanda bintang. Dan peta menjadi sbb.

*****.....
.X.X*.XXX.
.X*.X*....
.X*.X*....
***.X*....
.......XX.
..........

Jika kemudian masukan adalah NORTH maka hal seperti di atas dilakukan ke arah atas untuk masing-masing tanda bintang. Dan peta menjadi sbb.

*.*.**....
*X*X.*XXX.
*X*.X*....
*X*.X*....
....X.....
.......XX.
..........

Jika kemudian masukan adalah WEST maka hal seperti di atas dilakukan ke arah atas untuk masing-masing tanda bintang. Dan peta menjadi sbb.

*****.....
.X.X*.XXX.
.X..X.....
.X..X.....
....X.....
.......XX.
..........

Jika kemudian masukan adalah NORTH maka hal seperti di atas dilakukan ke arah atas untuk masing-masing tanda bintang. Dan peta menjadi sbb.

....*.....
.X.X..XXX.
.X..X.....
.X..X.....
....X.....
.......XX.
..........

Jika sinyal masukan sudah habis maka tanda-tanda bintang menyatakan semua kemungkinan mobil itu berada saat ini.