Bài 5.5. Bài tập cơ bản về Đệ quy

Chào mừng các bạn quay trở lại với chuỗi bài viết về Cấu trúc dữ liệu và Giải thuật! Hôm nay, chúng ta sẽ cùng nhau khám phá một trong những khái niệm mạnh mẽ và đôi khi hơi "xoắn não" trong lập trình: Đệ quy (Recursion).

Nếu bạn đã từng gặp một vấn đề mà lời giải cho nó... lại giống hệt như vấn đề ban đầu, chỉ với một phiên bản nhỏ hơn? Đó chính là lúc đệ quy tỏa sáng! Đệ quy là một kỹ thuật giải quyết vấn đề bằng cách chia nhỏ nó thành các vấn đề con tương tự, cho đến khi gặp một vấn đề đủ đơn giản để giải quyết trực tiếp.

Đệ quy là gì?

Nói một cách đơn giản, đệ quy là khi một hàm tự gọi chính nó trong quá trình thực hiện. Hãy tưởng tượng bạn đang tìm đường thoát khỏi một mê cung. Một chiến lược đệ quy có thể là: "Để thoát khỏi mê cung này, tôi chỉ cần thoát khỏi cái mê cung nhỏ hơn ngay trước mặt, rồi đi qua cánh cửa." Và để thoát khỏi mê cung nhỏ hơn đó, bạn lại áp dụng chiến lược tương tự cho một mê cung còn nhỏ hơn nữa, cho đến khi bạn chỉ còn cách cửa ra vài bước chân (trường hợp đơn giản nhất).

Hai thành phần "sống còn" của Đệ quy

Một hàm đệ quy hợp lệ bắt buộc phải có hai thành phần sau:

Trường hợp cơ sở (Base Case): Đây là điều kiện dừng của đệ quy. Khi hàm đạt đến trường hợp cơ sở, nó sẽ không gọi đệ quy nữa mà trả về một giá trị hoặc thực hiện một hành động cụ thể để "giải quyết" vấn đề ở mức đơn giản nhất. Trường hợp cơ sở là cực kỳ quan trọng để tránh việc hàm gọi chính nó vô hạn, dẫn đến lỗi tràn ngăn xếp (stack overflow).
Bước đệ quy (Recursive Step): Đây là phần hàm tự gọi chính nó. Trong bước này, hàm giải quyết một phần của vấn đề hiện tại và gọi đệ quy cho một phiên bản nhỏ hơn của vấn đề ban đầu. Điều quan trọng là vấn đề con phải tiến gần hơn đến trường hợp cơ sở sau mỗi lần gọi.

Nếu thiếu trường hợp cơ sở, đệ quy sẽ không bao giờ dừng. Nếu bước đệ quy không làm vấn đề nhỏ đi (hoặc làm nó nhỏ đi theo cách không hướng tới trường hợp cơ sở), nó cũng sẽ không dừng hoặc không giải quyết được vấn đề.

Đệ quy hoạt động như thế nào? (Lén nhìn vào Ngăn xếp)

Khi một hàm được gọi trong lập trình, hệ điều hành sẽ cấp phát một phần bộ nhớ trên ngăn xếp hàm gọi (call stack) cho hàm đó. Phần bộ nhớ này chứa các thông tin cần thiết như biến cục bộ, địa chỉ trả về sau khi hàm kết thúc...

Khi một hàm đệ quy gọi chính nó, một "bản sao" mới của hàm (với các tham số mới) sẽ được đẩy lên ngăn xếp. Quá trình này lặp đi lặp lại cho đến khi đạt đến trường hợp cơ sở.

Khi trường hợp cơ sở được xử lý và trả về giá trị, khung ngăn xếp của hàm gọi cuối cùng sẽ được giải phóng. Sau đó, hàm gọi trước đó trên ngăn xếp sẽ nhận được kết quả này, thực hiện các phép tính của nó và trả về kết quả của nó cho hàm gọi trước nữa. Quá trình "trả về" và giải phóng ngăn xếp này tiếp tục cho đến khi hàm đệ quy ban đầu (lần gọi đầu tiên) hoàn thành và trả về kết quả cuối cùng.

Hiểu được cơ chế ngăn xếp này giúp chúng ta hình dung được quá trình tính toán ngược dòng khi đệ quy "quay trở lại" sau khi chạm đáy (trường hợp cơ sở).

Các Ví dụ Minh họa Đệ quy cơ bản bằng C++

Để hiểu rõ hơn, chúng ta hãy xem xét một vài ví dụ kinh điển về đệ quy.

Ví dụ 1: Tính Giai thừa (Factorial)

Giai thừa của một số nguyên không âm n, ký hiệu là n!, được định nghĩa là tích của tất cả các số nguyên dương từ 1 đến n. Đặc biệt, 0! được định nghĩa là 1.

Công thức toán học của giai thừa có tính đệ quy rõ rệt:

n! = n * (n-1)! với n > 0
0! = 1

Đây chính là cấu trúc của đệ quy!

Trường hợp cơ sở: n == 0 hoặc n == 1, kết quả là 1.
Bước đệ quy: factorial(n) = n * factorial(n-1). Vấn đề con factorial(n-1) nhỏ hơn vấn đề gốc factorial(n) và tiến dần đến trường hợp cơ sở n=1 hoặc n=0.

Hãy cùng cài đặt bằng C++:

#include <iostream>

// Hàm tính giai thừa bằng đệ quy
long long factorial(int n) {
    // (*) Trường hợp cơ sở: Dừng lại khi n là 0 hoặc 1
    if (n == 0 || n == 1) {
        std::cout << "Reached base case for n = " << n << ", returning 1" << std::endl; // In ra để theo dõi
        return 1;
    }
    // (*) Bước đệ quy: Gọi lại hàm với tham số nhỏ hơn (n-1)
    else {
        std::cout << "Recursive step: factorial(" << n << ") calls factorial(" << n - 1 << ")" << std::endl; // In ra để theo dõi
        long long result_of_smaller_problem = factorial(n - 1); // Giải quyết vấn đề con
        long long final_result = n * result_of_smaller_problem; // Kết hợp kết quả vấn đề con
        std::cout << "Returning from factorial(" << n << "): " << final_result << std::endl; // In ra để theo dõi
        return final_result;
    }
}

int main() {
    int num = 5;
    if (num < 0) {
        std::cout << "Giai thua khong ton tai cho so am." << std::endl;
    } else {
        std::cout << "Bat dau tinh giai thua cua " << num << std::endl;
        long long result = factorial(num);
        std::cout << "Ket qua giai thua cua " << num << " la: " << result << std::endl; // Output: 120
    }

    // Thử với số khác
    std::cout << "\nBat dau tinh giai thua cua 0" << std::endl;
    std::cout << "Ket qua giai thua cua 0 la: " << factorial(0) << std::endl; // Output: 1

    return 0;
}

Giải thích Code:

Hàm factorial(int n) nhận vào một số nguyên n.
Dòng 8-11: Kiểm tra n == 0 hoặc n == 1. Đây là trường hợp cơ sở. Nếu đúng, hàm dừng đệ quy và trả về 1. Các câu lệnh std::cout được thêm vào để bạn dễ dàng theo dõi luồng thực hiện của hàm khi nó đi xuống và quay lên trên ngăn xếp.
Dòng 13-19: Nếu n lớn hơn 1, đây là bước đệ quy. Hàm in ra thông báo gọi đệ quy và sau đó gọi chính nó với tham số n - 1. Kết quả từ lời gọi đệ quy này (là factorial(n-1)) được nhân với n hiện tại trước khi trả về. Quá trình này lặp lại cho đến khi chạm trường hợp cơ sở.
Hàm main chỉ đơn giản gọi hàm factorial với một giá trị và in kết quả.

Khi bạn chạy code với factorial(5), luồng thực hiện (dựa vào các dòng in thêm) sẽ tương tự như sau:

Bat dau tinh giai thua cua 5
Recursive step: factorial(5) calls factorial(4)
Recursive step: factorial(4) calls factorial(3)
Recursive step: factorial(3) calls factorial(2)
Recursive step: factorial(2) calls factorial(1)
Reached base case for n = 1, returning 1
Returning from factorial(2): 2
Returning from factorial(3): 6
Returning from factorial(4): 24
Returning from factorial(5): 120
Ket qua giai thua cua 5 la: 120

Bat dau tinh giai thua cua 0
Reached base case for n = 0, returning 1
Ket qua giai thua cua 0 la: 1

Bạn có thể thấy rõ quá trình đi "sâu" vào các lời gọi đệ quy cho đến khi gặp n=1 (trường hợp cơ sở), sau đó "ngược" lên, tính toán và trả về kết quả ở mỗi cấp độ.

Ví dụ 2: Tính Số Fibonacci (Fibonacci Numbers)

Dãy Fibonacci là một dãy số bắt đầu bằng 0 và 1, các số tiếp theo bằng tổng của hai số liền trước. Dãy bắt đầu như sau: 0, 1, 1, 2, 3, 5, 8, 13, ...

Công thức toán học:

F(n) = F(n-1) + F(n-2) với n > 1
F(0) = 0
F(1) = 1

Đây cũng là một ví dụ điển hình cho đệ quy:

Trường hợp cơ sở: n == 0 (trả về 0) và n == 1 (trả về 1). Có hai trường hợp cơ sở.
Bước đệ quy: fibonacci(n) = fibonacci(n-1) + fibonacci(n-2). Vấn đề con fibonacci(n-1) và fibonacci(n-2) đều nhỏ hơn fibonacci(n) và tiến dần đến các trường hợp cơ sở 0 và 1.

Cài đặt bằng C++:

#include <iostream>

// Hàm tính số Fibonacci thứ n bằng đệ quy
int fibonacci(int n) {
    // (*) Trường hợp cơ sở: Dừng lại khi n là 0 hoặc 1
    if (n <= 1) {
        std::cout << "Reached base case for n = " << n << ", returning " << n << std::endl; // In ra để theo dõi
        return n;
    }
    // (*) Bước đệ quy: Tổng của hai số Fibonacci đứng trước
    else {
        std::cout << "Recursive step: fibonacci(" << n << ") calls fibonacci(" << n - 1 << ") and fibonacci(" << n - 2 << ")" << std::endl; // In ra để theo dõi
        int result = fibonacci(n - 1) + fibonacci(n - 2); // Giải quyết hai vấn đề con và cộng kết quả
        std::cout << "Returning from fibonacci(" << n << "): " << result << std::endl; // In ra để theo dõi
        return result;
    }
}

int main() {
    int num = 10; // Muốn tính số Fibonacci thứ 10
    if (num < 0) {
        std::cout << "So Fibonacci khong ton tai cho so am." << std::endl;
    } else {
        std::cout << "Bat dau tinh so Fibonacci thu " << num << std::endl;
        int result = fibonacci(num);
        std::cout << "So Fibonacci thu " << num << " la: " << result << std::endl; // Output: 55
    }

    // Thử với các số nhỏ hơn
    std::cout << "\nBat dau tinh so Fibonacci thu 0" << std::endl;
    std::cout << "So Fibonacci thu 0 la: " << fibonacci(0) << std::endl; // Output: 0

    std::cout << "\nBat dau tinh so Fibonacci thu 1" << std::endl;
    std::cout << "So Fibonacci thu 1 la: " << fibonacci(1) << std::endl; // Output: 1

    std::cout << "\nBat dau tinh so Fibonacci thu 2" << std::endl;
     std::cout << "So Fibonacci thu 2 la: " << fibonacci(2) << std::endl; // Output: 1


    return 0;
}

Giải thích Code:

Hàm fibonacci(int n) nhận vào chỉ số n của số Fibonacci cần tính.
Dòng 8-11: Đây là trường hợp cơ sở kép. Nếu n là 0 hoặc 1, hàm trả về chính n.
Dòng 13-18: Nếu n lớn hơn 1, đây là bước đệ quy. Hàm in thông báo gọi đệ quy, sau đó tự gọi chính nó hai lần với các tham số n - 1 và n - 2. Kết quả của hai lời gọi đệ quy này được cộng lại và trả về.
Hàm main gọi hàm fibonacci và in kết quả.

Khi chạy fibonacci(4) (để dễ theo dõi hơn là 10), luồng thực hiện (dựa vào các dòng in thêm) sẽ cho thấy cấu trúc cây của các lời gọi:

Bat dau tinh so Fibonacci thu 4
Recursive step: fibonacci(4) calls fibonacci(3) and fibonacci(2)
Recursive step: fibonacci(3) calls fibonacci(2) and fibonacci(1)
Recursive step: fibonacci(2) calls fibonacci(1) and fibonacci(0)
Reached base case for n = 1, returning 1
Reached base case for n = 0, returning 0
Returning from fibonacci(2): 1
Reached base case for n = 1, returning 1
Returning from fibonacci(3): 2
Recursive step: fibonacci(2) calls fibonacci(1) and fibonacci(0)
Reached base case for n = 1, returning 1
Reached base case for n = 0, returning 0
Returning from fibonacci(2): 1
Returning from fibonacci(4): 3
So Fibonacci thu 4 la: 3

Lưu ý quan trọng: Mặc dù giải thuật Fibonacci đệ quy này rất trực quan, nó lại kém hiệu quả vì tính toán lại các giá trị đã tính nhiều lần (ví dụ, fibonacci(2) được tính hai lần trong ví dụ trên). Đây là một nhược điểm tiềm ẩn của đệ quy "ngây thơ" mà chúng ta cần lưu ý. Các kỹ thuật như đệ quy có nhớ (memoization) hoặc sử dụng vòng lặp (lặp) thường được ưu tiên cho bài toán Fibonacci trong thực tế để cải thiện hiệu suất.

Ví dụ 3: Tính Tổng các Phần tử trong Mảng bằng Đệ quy

Chúng ta cũng có thể sử dụng đệ quy để thực hiện các thao tác trên cấu trúc dữ liệu như mảng. Hãy xem cách tính tổng các phần tử trong một mảng bằng đệ quy.

Ý tưởng đệ quy:

Tổng của mảng gồm n phần tử là bằng phần tử cuối cùng cộng với tổng của mảng gồm n-1 phần tử đầu tiên.
Tổng của mảng rỗng (0 phần tử) là 0.
Trường hợp cơ sở: Kích thước mảng con xét là 0, tổng là 0.
Bước đệ quy: sum(arr, n) = arr[n-1] + sum(arr, n-1). Vấn đề con sum(arr, n-1) nhỏ hơn sum(arr, n) và tiến dần đến trường hợp cơ sở (kích thước mảng con bằng 0).

Cài đặt bằng C++: (Chúng ta sẽ dùng std::vector để dễ thao tác hơn với kích thước)

#include <iostream>
#include <vector>
#include <numeric> // Bao gồm hàm std::accumulate để so sánh (không dùng trong đệ quy)

// Hàm tính tổng các phần tử trong vector bằng đệ quy
// Tham số: vector arr và kích thước hiện tại (hoặc số phần tử còn lại cần tính tổng)
int sumArrayRecursive(const std::vector<int>& arr, int size) {
    // (*) Trường hợp cơ sở: Nếu kích thước là 0 (mảng rỗng), tổng là 0
    if (size <= 0) {
        std::cout << "Reached base case with size = " << size << ", returning 0" << std::endl; // In ra để theo dõi
        return 0;
    }
    // (*) Bước đệ quy: Tổng = phần tử cuối cùng của tập hợp con + tổng của tập hợp con còn lại
    else {
        // arr[size - 1] là phần tử cuối cùng của vector con có kích thước 'size'
        std::cout << "Recursive step: sumArrayRecursive(..., " << size << ") calls sumArrayRecursive(..., " << size - 1 << ") and adds arr[" << size - 1 << "] (" << arr[size-1] << ")" << std::endl; // In ra để theo dõi
        int sum_of_rest = sumArrayRecursive(arr, size - 1); // Tính tổng phần còn lại
        int final_sum = arr[size - 1] + sum_of_rest; // Cộng với phần tử cuối
        std::cout << "Returning from sumArrayRecursive(..., " << size << "): " << final_sum << std::endl; // In ra để theo dõi
        return final_sum;
    }
}

int main() {
    std::vector<int> myVector = {1, 2, 3, 4, 5};
    int initial_size = myVector.size();

    std::cout << "Bat dau tinh tong vector: ";
    for(int x : myVector) std::cout << x << " ";
    std::cout << std::endl;

    int totalSum = sumArrayRecursive(myVector, initial_size);

    std::cout << "Tong cac phan tu trong mang la: " << totalSum << std::endl; // Output: 15

    // So sánh với cách thông thường (không dùng đệ quy)
    // int checkSum = std::accumulate(myVector.begin(), myVector.end(), 0);
    // std::cout << "Tong tinh bang accumulate (kiem tra): " << checkSum << std::endl;

    return 0;
}

Giải thích Code:

Hàm sumArrayRecursive nhận vector arr và size là số phần tử cần tính tổng từ đầu mảng.
Dòng 11-14: Trường hợp cơ sở: Khi size là 0 hoặc nhỏ hơn (đề phòng lỗi), tức là không còn phần tử nào để tính tổng, hàm trả về 0.
Dòng 16-23: Bước đệ quy: Hàm gọi chính nó với size - 1, tính tổng của tất cả trừ phần tử cuối cùng của tập hợp con hiện tại. Kết quả này được cộng với phần tử cuối cùng (arr[size - 1]) để có tổng của tập hợp con hiện tại và trả về.
Trong main, chúng ta gọi hàm với kích thước ban đầu của vector.

Luồng thực hiện (dựa vào các dòng in thêm) cho myVector = {1, 2, 3, 4, 5}:

Bat dau tinh tong vector: 1 2 3 4 5
Recursive step: sumArrayRecursive(..., 5) calls sumArrayRecursive(..., 4) and adds arr[4] (5)
Recursive step: sumArrayRecursive(..., 4) calls sumArrayRecursive(..., 3) and adds arr[3] (4)
Recursive step: sumArrayRecursive(..., 3) calls sumArrayRecursive(..., 2) and adds arr[2] (3)
Recursive step: sumArrayRecursive(..., 2) calls sumArrayRecursive(..., 1) and adds arr[1] (2)
Recursive step: sumArrayRecursive(..., 1) calls sumArrayRecursive(..., 0) and adds arr[0] (1)
Reached base case with size = 0, returning 0
Returning from sumArrayRecursive(..., 1): 1
Returning from sumArrayRecursive(..., 2): 3
Returning from sumArrayRecursive(..., 3): 6
Returning from sumArrayRecursive(..., 4): 10
Returning from sumArrayRecursive(..., 5): 15
Tong cac phan tu trong mang la: 15

Quá trình này cho thấy hàm đi xuống đến khi xét tập hợp con rỗng, trả về 0. Sau đó quay ngược lên, lần lượt cộng các phần tử 1, 2, 3, 4, 5 vào tổng đang tích lũy.

Đệ quy hay Lặp (Iteration)?

Đệ quy và lặp (sử dụng vòng lặp for, while) là hai cách tiếp cận khác nhau để giải quyết các vấn đề lặp đi lặp lại.

Đệ quy thường dẫn đến code ngắn gọn, thanh lịch và gần gũi với định nghĩa toán học của vấn đề (như giai thừa, Fibonacci). Nó rất tự nhiên khi làm việc với các cấu trúc dữ liệu đệ quy như cây (tree) hoặc đồ thị (graph).
Lặp thường hiệu quả hơn về mặt bộ nhớ (không tốn chi phí cho ngăn xếp hàm gọi) và tốc độ (không có overhead gọi hàm). Nó thường dễ kiểm soát và gỡ lỗi hơn trong nhiều trường hợp đơn giản.

Nhiều bài toán có thể giải bằng cả hai cách. Việc lựa chọn tùy thuộc vào tính chất bài toán, hiệu suất yêu cầu và sự rõ ràng của code. Đối với các bài toán đơn giản như giai thừa, lặp thường được ưu tiên vì hiệu quả. Đối với các bài toán phức tạp hơn như duyệt cây, đệ quy thường cung cấp lời giải thanh lịch và dễ hiểu hơn.

Tóm tắt cách tiếp cận bài toán bằng Đệ quy

Khi đứng trước một bài toán và muốn thử giải bằng đệ quy, hãy suy nghĩ theo các bước sau:

Xác định Trường hợp cơ sở (Base Case): Đâu là trường hợp đơn giản nhất của bài toán mà bạn có thể giải quyết trực tiếp mà không cần gọi đệ quy? Kết quả ở trường hợp này là gì?
Xác định Bước đệ quy (Recursive Step): Giả sử bạn đã có thể giải quyết vấn đề cho một phiên bản nhỏ hơn của bài toán, làm thế nào để sử dụng kết quả đó để giải quyết vấn đề lớn hơn hiện tại?
Đảm bảo Tiến gần Trường hợp cơ sở: Mỗi bước đệ quy bạn thực hiện có làm cho bài toán con nhỏ hơn và tiến gần hơn đến trường hợp cơ sở hay không? Nếu không, đệ quy của bạn có thể sẽ không dừng lại.

Bài tập ví dụ:

Vượt Ngục 2

Trong một buổi hẹn hò lãng mạn, FullHouse Dev đã kể cho người yêu nghe về một bài toán thú vị về tù nhân Alfie. Alfie, một người thông minh và mưu trí, đang tìm cách vượt ngục khỏi nhà tù huyền thoại. Sau nhiều ngày quan sát, anh ta phát hiện nhà tù có cấu trúc là một ma trận \(N \times N\). Một số ô trong nhà tù được lắp đặt cảm biến chuyển động. Alfie cần tính toán số lượng đường đi khác nhau để thoát khỏi nhà tù mà không chạm vào các cảm biến.

INPUT FORMAT:

Dòng đầu tiên chứa số nguyên \(T\) - số lượng test case
Dòng đầu tiên của mỗi test case chứa số nguyên \(N\) (kích thước ma trận \(N \times N\))
\(N\) dòng tiếp theo, mỗi dòng chứa \(N\) số, mỗi số là 0 hoặc 1 (1 đại diện cho ô có cảm biến chuyển động)

OUTPUT FORMAT:

Với mỗi test case, in ra số lượng đường đi khác nhau có thể để thoát khỏi nhà tù

Lưu ý:

Alfie bắt đầu từ ô \((1,1)\) và cần đến ô \((N,N)\)
Alfie có thể di chuyển theo 4 hướng: lên, xuống, trái, phải
Nếu ô đầu tiên \((1,1)\) hoặc ô cuối cùng \((N,N)\) có cảm biến, Alfie không thể thoát được

Ví dụ

INPUT

OUTPUT

2
4
4

Giải thích

Trong test case đầu tiên, có 2 đường đi khả thi để Alfie thoát khỏi nhà tù mà không chạm vào cảm biến
Trong test case thứ hai và ba, có 4 đường đi khả thi cho mỗi trường hợp

Ràng buộc:

\(1 \leq T \leq 100\)
\(2 \leq N \leq 10\)
Ma trận chỉ chứa giá trị 0 và 1 Okay, đây là hướng dẫn giải bài "Vượt Ngục 2" bằng C++ một cách ngắn gọn:

Nhận dạng bài toán: Đây là bài toán đếm số lượng đường đi trong ma trận có chướng ngại vật, cho phép di chuyển 4 hướng (lên, xuống, trái, phải).
Thuật toán phù hợp: Với kích thước ma trận nhỏ (N <= 10) và yêu cầu đếm tất cả các đường đi (kể cả đường đi có thể quay lại các ô đã thăm trước đó nhưng không phải trong cùng một nhánh đệ quy để tránh lặp vô hạn), phương pháp Tìm kiếm theo chiều sâu (DFS - Depth First Search) hoặc Quay lui (Backtracking) là phù hợp nhất.
Ý tưởng DFS/Backtracking:
- Bắt đầu từ ô (0, 0) (tương ứng (1,1) trong đề bài).
- Sử dụng đệ quy để duyệt qua các ô lân cận hợp lệ.
- Một ô hợp lệ là ô:
  - Nằm trong phạm vi ma trận (0 <= row < N, 0 <= col < N).
  - Không phải là ô có cảm biến (grid[row][col] == 0).
  - Quan trọng: Chưa được thăm trong đường đi hiện tại để tránh lặp vô hạn (đi tới đi lui giữa hai ô trống).
State của đệ quy: Hàm đệ quy cần biết vị trí hiện tại (row, col). Nó cũng cần truy cập vào ma trận grid và kích thước N. Để theo dõi các ô đã thăm trong đường đi hiện tại, cần một ma trận visited cùng kích thước.
Các bước thực hiện trong hàm đệ quy (ví dụ solve(row, col, N, grid, visited)):
- Kiểm tra điều kiện dừng (Base Cases):
  - Nếu row, col nằm ngoài phạm vi ma trận hoặc ô grid[row][col] có cảm biến (== 1) hoặc ô visited[row][col] đã được đánh dấu là true (đã thăm trong đường đi này): Trả về 0 (không có đường đi từ đây).
  - Nếu row == N-1 và col == N-1 (đã đến ô đích): Trả về 1 (tìm thấy 1 đường đi hợp lệ).
- Đánh dấu: Đánh dấu ô hiện tại (row, col) là đã thăm trong đường đi này: visited[row][col] = true.
- Duyệt các hướng: Khởi tạo biến đếm tổng số đường đi từ ô này (count = 0).
  - Duyệt qua 4 hướng di chuyển (lên, xuống, trái, phải).
  - Đối với mỗi hướng, tính toán vị trí ô kế tiếp (next_row, next_col).
  - Gọi đệ quy: count += solve(next_row, next_col, N, grid, visited).
- Quay lui (Backtrack): Sau khi đã thử hết các hướng từ ô hiện tại, cần bỏ đánh dấu ô này: visited[row][col] = false. Bước này cực kỳ quan trọng để các đường đi khác có thể đi qua ô này.
- Trả về: Trả về count (tổng số đường đi hợp lệ từ ô (row, col) đến đích).
Hàm chính:
- Đọc T. Lặp T lần.
- Trong mỗi test case:
  - Đọc N và ma trận grid[N][N].
  - Kiểm tra điều kiện đặc biệt: Nếu grid[0][0] == 1 hoặc grid[N-1][N-1] == 1, in ra 0 và chuyển sang test case tiếp theo.
  - Khởi tạo ma trận visited[N][N] với tất cả giá trị là false.
  - Gọi hàm đệ quy từ điểm bắt đầu: result = solve(0, 0, N, grid, visited).
  - In ra result.
Lưu ý triển khai:
- Sử dụng mảng 2D (ví dụ int grid[10][10], bool visited[10][10]) hoặc vector<vector<int>> và vector<vector<bool>>. Do N nhỏ, cả hai cách đều được.
- Mảng/vector cho 4 hướng di chuyển có thể giúp code gọn gàng hơn (ví dụ: dr[] = {-1, 1, 0, 0}, dc[] = {0, 0, -1, 1}).

Làm thêm nhiều bài tập miễn phí tại đây

Comments

There are no comments at the moment.