BacktrackingMenengahFase D–FE1E5

RAT MAZE

Rat Maze menyelesaikan labirin dengan backtracking: tikus maju sel demi sel menandai jalur, dan bila menemui jalan buntu atau sel terhalang, ia mundur (menghapus sel dari path) lalu mencoba arah lain. Proses maju-mundur-coba lagi berlanjut sampai sel keluar (exit) tercapai. Visualisasi menampilkan jalur yang dijelajahi, sel yang ditolak/di-backtrack, hingga jalur solusi akhir terkunci.

Example use case

Penyelesaian labirin otomatis atau robot penelusur maze yang mencoba tiap cabang dan mundur saat menemui jalan buntu.

Syllabus

Rat in a Maze menyelesaikan labirin dengan backtracking: tikus maju menandai jalur dan mundur mencoba arah lain saat mentok.

Objectives

·Memahami cara menandai dan membatalkan jalur saat menjelajah
·Menjelaskan pola maju-mundur-coba lagi pada backtracking
·Menerapkan backtracking untuk menemukan jalur keluar labirin

How It Works

·Tikus maju satu sel dan menandainya sebagai bagian jalur
·Coba arah berikutnya yang bebas dan belum dilewati
·Bila menemui jalan buntu atau sel terhalang, mundur
·Hapus sel dari jalur saat mundur lalu coba arah lain
·Ulangi sampai sel keluar (exit) tercapai dan jalur solusi terbentuk

Prerequisites

·Backtracking
·Grid 2D

Real-World Uses

·Robot penelusur maze mencoba tiap cabang dan mundur saat buntu
·Penyelesaian labirin otomatis di game teka-teki
·Mencari jalan keluar pada peta bercabang secara sistematis

Complexity O(4^(m x n)) pada kasus terburuk