Labirentteki Fare

Geri İzleme O(4^(N²)) O(N²)

Bir ızgarada sol üstten sağ alta bir yol bulur; rotayı işaretler ve çıkmazlarda geri alır.

Fare sol üstten başlar, çıkış sağ alttadır. Duvarlar koyu hücrelerdir.

1/52

(0, 0) konumuna adım atılıyor.

Değişmezİşaretli gözler girişten mevcut göze kadar tek bir açık yol oluşturur, tekrar içermez.

deneniyoryoldaçıkmazgeri izleme

rat-in-a-maze.c

#define N 4
 
int solve(int maze[N][N], int r, int c, int sol[N][N]) {
    if (r < 0 || c < 0 || r >= N || c >= N ||
        maze[r][c] == 0 || sol[r][c] == 1)
        return 0;
 
    sol[r][c] = 1;
    if (r == N - 1 && c == N - 1)
        return 1;   /* exit reached */
 
    if (solve(maze, r + 1, c, sol)) return 1;   /* down  */
    if (solve(maze, r, c + 1, sol)) return 1;   /* right */
    if (solve(maze, r - 1, c, sol)) return 1;   /* up    */
    if (solve(maze, r, c - 1, sol)) return 1;   /* left  */
    sol[r][c] = 0;   /* backtrack */
    return 0;
}

Labirentteki Fare nasıl çalışır?

Her hücrede dört yönü sabit sırayla dene, giderken yolu işaretle, geri çekilirken sil. İşaretler ziyaret kontrolü olarak da çalışır; arama asla döngüye girmez.

Ne zaman kullanılır?

Izgaralarda yol varlığı ve basit labirent çözümü; ızgarada BFS/DFS'e geçiş taşı.