Pembahasan Soal labirin

Ini memang soal yang paling sulit di antara semua soal yang diberikan. Namun, ternyata anda masih bisa memecahkannya jika bisa memahami penjelasan sbb ini.

Masalah ini termasuk masalah graph traversal dengan metoda breadth first search (BFS). Untuk memudahkan pemahaman anda, pertama kita membahas kasus tanpa adanya switch. Dengan tidak adanya variabel-variabel switch maka anda bisa mengimplementasikan BFS (hanya dengan sejumlah modifikasi kecil) pada graph dengan verteks-verteks graph adalah ruang-ruang dan lorong-lorong penghubung adalah edge-edge graph.

Untuk submasalah ini BFS memerlukan suatu queue untuk menyimpan verteks-verteks pada breadth yang akan ditraverse berikutnya. Algoritma BFS untuk masalah ini tanpa switch adalah sbb. (Warning: algoritma ini adalah pascal-like pseudocode, bukan Pascal code, jadi harap anda memaklumi kalau ada syntax error!).

function labirin(Start: vertex, Target: vertex): integer;
var 
    Q: queue;
    qe,qe2: queueElement;
    i,adjlen: integer;
begin
    initQueue(Q); {mengosongkan queue}
    qe.room := Start;
    qe.pathlen := 0;
    putInQueue(Q, qe);

    while (notEmpty(Q)) begin
        qe := getQueue(Q);
        if (qe.room = Target) begin
             labirin := qe.pathlen;
             exit;
        end;
	p = getUnvisitedUnlockedAdjacentRoom(qe, S adjlen);
        for i := 1 to adjlen do begin
            qe2.room := p[i];
            qe2.pathlen := qe.pathlen + 1;
            putInQueue(Q,qe2);
        end;
    end;
    
end;

Nah sekarang, untuk kasus dengan adanya switch maka kerumitannya meningkat sbb. Setiap ruang memiliki status locked atau unlocked yang dapat secara dinamis berubah-ubah sesuai dengan penekanan tombol yang mempengaruhinya. Kita coba melihat masalah sbb. Satu verteks bukan lagi satu ruang, tetapi suatu ruang dengan status S switch yang berbeda sebagai suatu vektor (noruang, s₁s₂...s_S). Setiap switch memiliki harga biner 0 dan 1. Harga switch = 0 jika penekanan switch dilakukan dalam jumlah yang genap, dan = 1 jika ganjil. Deratan harga switch s₁s₂..s_S ini membentuk suatu bilangan yang kita sebut X. karena soal membatasi S <= 8, maka 0 ≤ X < 256.

Jadi, untuk N ruang dan S switch akan ada Nx2^S verteks yang berbeda. Sementara untuk graph tanpa adanya switch hanya berisi N verteks. Untuk memudahkan pembahasan kita selanjutnya menyebut graph tanpa switch tsb sebagai plain graph.

Untuk masalah dengan switch ini graph berbentuk multilayer graph sbb. Jika jumlah switch adalah S maka jumlah layer adalah 2^S. Layer pertama adalah plain graph dengan adanya X=0. Setiap layer berikutnya adalah juga plain graph dengan harga X yang berbeda (tapi sama pada layer yang sama!). Jika dalam plain graph terdapat edge antara vi dan vj maka juga ada dalam (vi,X) dengan (vj,X). Sementara keterhubungan antara layer: jika pada Vi tdp switch (dalam soal dibatasi i <= S), maka terdapat edge antara (vi,X1) dan (Vi, X2) dengan X1 dan X2 hanya berbeda tepat di bit ke-i. Karena edge antara layer ini masih di ruangan yang sama maka dalam penghitungan jumlah lorong yang dilalui, edge ini tidak termasuk yang dihitung.

Dalam implementasinya multilayer graph ini cukup diwakili oleh satu plain graph (untuk memeriksa keterhubungan antar ruangan) dengan harga-harga (Vi,X) disimpan dalam tabel. Karena jumlah verteks plain graph maksimum 100 dan S paling banyak 8 maka untuk menghemat memory (Vi,X) bisa direpresentasikan sebagai index dari array status dengan panjang maxsimum 25600. Untuk mendapatkan harga komponennya maka dari harga indeks tsb anda dapat gunakan operasi-operasi and/or/xor/mod/div. Array status tsb bisa digunakan untuk mencatat pathlen dan status visited.

Apalagi ya?? Hmm. bagaimana perubahan lock-unlock suatu ruangan dapat diikuti? Misalkan ruangan J. Jika berada pada harga switch X= s₁, s₂, ..., s_S maka untuk setiap bit s_i = 1 dari X dan switch di ruang-i mempengaruhi ruang J tsb maka status lock dari ruangan tsb (variabel lockstate) ditoggle:
lockstate := not lockstate. Misalnya s1, s4 dan s8 yang berharga 1. Kita periksa apakah switch di ruang 1, 4 dan 8 mempengaruhi J? Jika hanya 1 dan 4 yang mempengaruhi J berarti ruang J di toggle dua kali alias kembali seperti semula. Jika ketiganya mempengaruhi J maka status ruang J kebalikan dari semula. Pemeriksaan tersebut saat menjalankan getUnvisitedAdjacentRoom dilakukan. Jika verteks berikutnya dalam status locked maka tentu tidak dapat dimasukan ke dalam queue.

Ok, sekarang kita lihat contoh masukan pertama dari soal.

4 1
0 1 3
1 2 3 4
0 2 1 2
0 1 2
1 2
3 4