Lingkaran Warna

Kali ini kita membahas soal di http://acm.uva.es/p/v8/899.html tentang permainan menggunakan lingkaran berwarna. Di sini bermain 2 orang yang saling bergantian berpindah arah. Tujuannya sederhana, yaitu mencapai lingkaran tujuan dengan pergerakan minimal. Meskipun soal ini tampak biasa-biasa saja, tapi cukup baik sebagai contoh penggunaan fungsi / prosedur rekursif. Rekursif berarti memanggil dirinya sendiri. Pada banyak bahasa pemrograman kemampuan untuk rekursif ini sangat membantu dalam menyederhanakan logika program. Dari soal yang disajikan kurang lebih ada aturan berikut:

  • Terdapat lingkaran dari 1 s/d 100.
  • Tiap lingkaran memiliki warna dan dimungkinkan terdapat duplikasi.
  • Terdapat panah-panah yang menghubungkan dari satu lingkaran ke lingkaran yang lain. Panah tersebut berisi data: dari, ke, dan warna.

Dalam melakukan pergerakan terdapat aturan berikut:

  • Lingkaran tujuan ditentukan oleh panah yang warnanya sesuai lingkaran di mana posisi lawan berada. Misal: ketika A di Lingkaran Merah dan B di Lingkaran Biru, maka A bergerak sesuai arah panah berwarna Biru, demikian sebaliknya B bergerak sesuai arah panah berwarna merah.
  • Perkecualian bila lingkaran yang dituju telah ditempati oleh lawan yang berarti arah tersebut tidak valid.
  • Dalam 1 giliran dapat terjadi banyak perpindahan hingga tidak dimungkinkan lagi untuk berpindah.

Format Input

Format input terdiri dari beberapa baris. Pada baris pertama terdiri dari N, R, S, T and M, yang artinya:

  • N: banyaknya lingkaran.
  • R dan S: lingkaran awal dari pemain A dan B.
  • T: lingkaran tujuan.
  • M: banyaknya panah.

Pada baris selanjutnya adalah warna dari tiap-tiap lingkaran. Sebanyak M baris berikutnya adalah data masing-masing panah. Data input ini berulang hingga semua baris selesai dibaca. Misal untuk satu permainan dengan 4 panah, maka dibutuhkan 1 + 1 + 4 baris data. Input berakhir setelah pada baris pertama terdiri dari 5 angka 0.

Pembacaan angka dalam Pascal sangat mudah, yaitu dengan ReadLn(Angka) atau Read(Angka). Batas pemisah dari tiap-tiap angka adalah while space, yaitu spasi (#32), Tab (#9), CR (#13), atau LF (#10). Bila pembacaan deretan angka menggunakan Read telah sampai akhir baris, dia secara otomatis akan naik ke baris berikutnya.

Struktur Data

Penyelesaian dari soal ini dimulai dengan penyusunan struktur data yang baik. Dari aturan-aturan di atas kita buat 2 jenis record, yaitu mewakili Panah dan Lingkaran. Banyaknya lingkaran dan panah ditentukan secara statis lewat konstanta.

const
MaxLingkaran = 100; 
type
TPanah = record
Warna, Arah: Byte;
end;
  TLingkaran = record
Warna: Byte;
    Banyak: Integer;
    Panah: array[1..MaxLingkaran+1] of TPanah;
end; 
var
Lkr: array[1..MaxLingkaran] of TLingkaran;

Warna dalam record tersebut hanya berukuran 1 byte karena maksimal lingkaran adalah 100. Begitu pula dengan Arah yang hanya berukuran 1 byte yang menentukan tujuan tidak lebih dari 100 lingkaran. Namun dalam penerjemahan kode TPanah ini akan berukuran minimal 4 byte karena default dari record alignment adalah 4 byte.

Dalam tiap-tiap lingkaran terdapat array Panah yang menunjukkan kemungkinan arah dari lingkaran tersebut menuju lingkaran yang lain. Array Panah ini lebih banyak 1 dari maksimal lingkaran sebagai batas arah yang valid. Dalam procedure Susur digunakan Warna = 0 untuk menunjukkan bahwa itu adalah akhir dari array Panah dalam sebuah Lingkaran.

Untuk menandai suatu Panah telah digunakan, dalam proses mencari kemungkinan arah menuju Lingkaran tujuan, digunakan bit ke-7 (susunan 0..7, nilainya 128) dari Warna, yaitu dengan meng-or-kan sebelum melakukan penelusuran, dan meng-and-kan setelah penelusuran. Dengan begitu dari pengecekan Warna sudah mencukupi apakah arahnya sesuai dan dapat digunakan. Prosedur Rekursif Inti dari penyelesaian soal ini terletak dalam procedure Susur, dengan parameter:

  • Cah, untuk banyaknya pergerakan. Setiap kali pemanggilan maka parameter ini akan dinaikkan dengan 1.
  • Ca, untuk posisi A saat ini.
  • Cb, untuk posisi B saat ini.

Yang perlu diperhatikan dalam pemakaian fungsi / prosedur rekursif adalah penggunaan variabel lokal yang efisien. Prosedur rekursif menggunakan stack sebagai penampung variabel lokal termasuk alamat kembali dari prosedur itu. Stack besarnya terbatas dan ditentukan pada saat kompilasi program.

Hal lain dalam prosedur rekursif adalah akhir dari prosedur tersebut untuk tidak melakukan perulangan lagi atau berhenti memanggil dirinya sendiri. Bila hal ini dilupakan maka prosedur akan terus berulang tanpa batas atau hingga kehabisan stack. Dalam procedure Susur ini akhir dari perulangan adalah apabila lingkaran tujuan tercapai atau banyaknya pergerakan lebih besar dari hasil sebelumnya.

Rutin yang berulang terdapat dalam procedure Susur, yaitu mewakili pergerakan A dan pergerakan B. Digunakan pointer Panah (^TPanah) sebagai wujud dari panah yang menunjukkan warna dan arah. Panah ini akan berubah-ubah sesuai penelusuran lingkaran hingga sampai ke lingkaran tujuan.

Program Lengkap

Bentuk lengkap dari penyelesaian soal 899 ini sebagai berikut.

program color_circle; 
const
MaxLkr = 100; 
type
TPanah = record
Warna, Arah: Byte;
end;
  TLkr = record
Warna: Byte;
    Banyak: Integer;
    Panah: array[1..MaxLkr+1] of TPanah;
end; 
var
Lkr: array[1..MaxLkr] of TLkr;
  BnLkr, BnPan, CahMax: Integer;
  Tuju: Byte; 
procedure Susur(Cah, Ca, Cb: Integer);
var
P: ^TPanah;
  Warna: Byte;
begin
P := @Lkr[Ca].Panah;
  Warna := Lkr[Cb].Warna;
while P^.Warna <> 0 do begin
    if (P^.Warna = Warna) and (P^.Arah <> Cb) then begin
      if P^.Arah = Tuju then begin
CahMax := Cah; Exit;
end;
if Cah < CahMax then begin
P^.Warna := P^.Warna or 128;
        Susur(Cah+1, P^.Arah, Cb);
        P^.Warna := P^.Warna and 127;
end;
end;
    Inc(P);
end;
  P := @Lkr[Cb].Panah;
  Warna := Lkr[Ca].Warna;
while P^.Warna <> 0 do begin
    if (P^.Warna = Warna) and (P^.Arah <> Ca) then begin
      if P^.Arah = Tuju then begin
CahMax := Cah; Exit;
end;
if Cah < CahMax then begin
P^.Warna := P^.Warna or 128;
        Susur(Cah+1, P^.Arah, Ca);
        P^.Warna := P^.Warna and 127;
end;
end;
    Inc(P);
end;
end; 
var
I, J, Cah1, Cah2: Integer;
begin
Readln(BnLkr, Cah1, Cah2, Tuju, BnPan);
while BnLkr > 0 do begin
    for I := 1 to BnLkr do begin
Read(Lkr[I].Warna);
      Lkr[I].Banyak := 0;
end;
for I := 1 to BnPan do begin
Read(J);
with Lkr[J] do begin
Inc(Banyak);
        Read(Panah[Banyak].Arah, Panah[Banyak].Warna);
end;
end;
for I := 1 to BnLkr do
Lkr[I].Panah[Lkr[I].Banyak+1].Warna := 0;
    CahMax := MaxInt;
    Susur(1, Cah1, Cah2);
if CahMax = MaxInt then Writeln(’0’) else Writeln(CahMax);
    Readln(BnLkr, Cah1, Cah2, Tuju, BnPan);
end;
end.

Demikian selamat mencoba.

2 Komentar »

  1. iwanmalik said

    Salam kenal
    http://iwanmalik.wordpress.com
    Terapkan ilmu dalam perbuatan

  2. Lego Haryanto said

    Rupanya Mpu penggemar programming contest problems juga … nice …

    Salam kenal,
    -Lego

RSS feed for comments on this post

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s