C++ Rat in a Maze หลายขั้นตอนหรือกระโดดได้

กำหนดกริด maze ขนาด n×n หนูของเราอยู่ที่มุมซ้ายบนของกริด ตอนนี้หนูสามารถเคลื่อนที่ลงหรือขวาได้ก็ต่อเมื่อบล็อกนั้นมีค่าไม่เป็นศูนย์ ตอนนี้ใน variation นี้ หนูได้รับอนุญาตให้กระโดดหลายขั้นตอน จำนวนขั้นตอนสูงสุดที่หนูสามารถกระโดดจากเซลล์ปัจจุบันคือตัวเลขที่อยู่ในเซลล์ และตอนนี้คุณถูกมอบหมายให้หาว่าหนูสามารถไปถึงมุมขวาล่างของกริดได้หรือไม่ ตัวอย่างเช่น:

Input : { { {1, 1, 1, 1}, {2, 0, 0, 2}, {3, 1, 0, 0}, {0, 0, 0, 1} } }
Output : { {1, 1, 1, 1}, {0, 0, 0, 1}, {0, 0, 0, 0}, {0, 0, 0, 1} }

Input : { {2, 1, 0, 0}, {2, 0, 0, 1}, {0, 1, 0, 1}, {0, 0, 0, 1} }
Output: Path doesn't exist

วิธีการหาคำตอบ

ในวิธีนี้ เราจะใช้ backtracking เพื่อติดตามทุกเส้นทางที่หนูสามารถเดินได้ ตอนนี้ถ้าหนูถึงจุดหมายจากเส้นทางใดเส้นทางหนึ่ง เราจะคืนค่า true สำหรับเส้นทางนั้นและพิมพ์เส้นทาง มิฉะนั้น เราพิมพ์ว่าเส้นทางไม่มีอยู่

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;

#define N 4 // ขนาดของกริดของเรา

bool solveMaze(int maze[N][N], int x, int y, int sol[N][N]){
    if (x == N - 1 && y == N - 1) { // ถ้าเราถึงเป้าหมาย คืน true และ mark เป้าหมายเป็น 1
        sol[x][y] = 1;
        return true;
    }
    if (x >= 0 && y >= 0 && x < N && y < N && maze[x][y]) {
        sol[x][y] = 1; // เรารวมดัชนีนี้เป็นเส้นทาง
        for (int i = 1; i <= maze[x][y] && i < N; i++) { // maze[x][y] แสดงจำนวนครั้งที่คุณสามารถกระโดดได้
            // ดังนั้นเราตรวจสอบการกระโดดทุกครั้งในทุกทิศทาง
            if (solveMaze(maze, x + i, y, sol) == true) // กระโดดขวา
                return true;
            if (solveMaze(maze, x, y + i, sol) == true) // กระโดดลง
                return true;
        }
        sol[x][y] = 0; // ถ้าไม่มีอันไหนเป็น true เส้นทางไม่มีอยู่
                       // หรือเส้นทางไม่มีเซลล์ปัจจุบันในมัน
        return false;
    }
    return false;
}

int main(){
    int maze[N][N] = { { 2, 1, 0, 0 }, { 3, 0, 0, 1 },{ 0, 1, 0, 1 }, { 0, 0, 0, 1 } };
    int sol[N][N];
    memset(sol, 0, sizeof(sol));
    if(solveMaze(maze, 0, 0, sol)){
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++)
                cout << sol[i][j] << " ";
            cout << "\n";
        }
    }
    else
        cout << "Path doesn't exist\n";
    return 0;
}

ผลลัพธ์

1 0 0 0
1 0 0 1
0 0 0 1
0 0 0 1

คำอธิบายโค้ด

ในวิธีข้างต้น เราตรวจสอบทุกเส้นทางที่มันสามารถทำได้จากเซลล์ปัจจุบันของเรา และขณะที่เราตรวจสอบ เรา mark เส้นทางเป็น 1 ตอนนี้เมื่อเส้นทางของเราถึง dead-end เราตรวจสอบว่า dead-end นั้นคือจุดหมายของเราหรือไม่ ตอนนี้ถ้ามันไม่ใช่จุดหมาย เรา backtrack และขณะที่เรา backtrack เรา mark เซลล์เป็น 0 เพราะเส้นทางนี้ไม่ถูกต้อง และนี่คือวิธีที่โค้ดของเราดำเนินการ

สรุป

ในบทช่วยสอนนี้ เราแก้ปัญหา Rat in a Maze ด้วยหลายขั้นตอนหรือกระโดดได้ เรายังเรียนรู้โปรแกรม C++ สำหรับปัญหานี้และวิธีการแก้ปัญหาแบบเต็มรูปแบบ (ปกติ) ที่เราใช้แก้ปัญหานี้ เราสามารถเขียนโปรแกรมเดียวกันในภาษาอื่นๆ เช่น C, Java, Python และภาษาอื่นๆ ได้ เราหวังว่าบทช่วยสอนนี้จะเป็นประโยชน์