Langkah Kuda
Hitung langkah paling sedikit bagi kuda catur untuk mencapai kotak tujuan.
Kuda catur bergerak membentuk huruf L: dua kotak ke satu arah, lalu satu kotak ke samping. Di papan berukuran N × N, berapa langkah paling sedikit yang dibutuhkan kuda dari kotak awal ke kotak tujuan?
Masukan
Baris pertama berisi N (1 sampai 100). Baris kedua berisi baris dan kolom kotak awal, lalu baris dan kolom kotak tujuan, semuanya dihitung dari 1.
Keluaran
Banyak langkah paling sedikit, atau -1 bila kotak tujuan tidak bisa dicapai.
Contoh masukan dan keluaran
Contoh 1
Masukan
8 1 1 8 8
Keluaran
6
Petunjuk
Coba kerjakan dulu. Buka petunjuk satu per satu kalau kamu buntu.
Petunjuk 1
Setiap kotak adalah simpul, dan delapan gerakan L adalah sisinya. Jarak terpendek di graf seperti ini dicari dengan BFS.
Petunjuk 2
Di papan yang sangat kecil, misalnya 3 × 3, kotak tengah tidak bisa dicapai sama sekali. Jangan lupa kasus itu.