Cần tìm cách để xử lý BFS của ma trận

[sabertoaster (Saber)]

Cho em hỏi thuật toán của một bài như sau ạ :
Cho một ma trận nxn, hãy tìm ra tất cả các đường đi xuất phát từ [1;1] tới [n;1] mà đi qua tất cả phần tử của ma trận. Dùng BFS hoặc DFS đều được ạ.
vd với ma trận 3x3 thì ta có 2 cách như sau :

[tntxtnt]

DFS bình thường thôi:

thêm thắt chỗ kiểm tra khi tới (n,1) thì cộng 1 nếu tổng đoạn đường đi được là n*n, và phải xóa visited[r][c] = false; để đếm tất cả đoạn đường

#include <iostream>
#include <vector>

struct HamiltonPathsNxNGridNwToSw {
    explicit HamiltonPathsNxNGridNwToSw(int n)
    : visited(n, std::vector<bool>(n, false)) {
        visit(0, 0, 1);
    }
    auto count() const -> int { return accm; }

private:
    void visit(int r, int c, int w) {
        int n = visited.size();
        if (r == n - 1 && c == 0) {
            accm += static_cast<int>(w == n * n);
            return;
        }
        visited[r][c] = true;
        if (r > 0 && !visited[r - 1][c]) visit(r - 1, c, w + 1);
        if (c > 0 && !visited[r][c - 1]) visit(r, c - 1, w + 1);
        if (r + 1 < n && !visited[r + 1][c]) visit(r + 1, c, w + 1);
        if (c + 1 < n && !visited[r][c + 1]) visit(r, c + 1, w + 1);
        visited[r][c] = false;
    }

    std::vector<std::vector<bool>> visited;
    int accm = 0;
};

auto main() -> int {
    for (int n = 1; n <= 6; ++n)
        std::cout << n << " " << HamiltonPathsNxNGridNwToSw{n}.count() << "\n";
}

chạy tới n=6 in ra kết quả là

1 1
2 1
3 2
4 8
5 86
6 1770

code này đếm tới n=6 là hết xí quách n=7 chạy tới hơn 5 giây. Tuy nhiên nếu đem dãy số 1 1 2 8 86 1770 vào search trong OEIS thì ra dãy này: https://oeis.org/A000532/ trong đó chạy tới n=18 là hết cỡ :V Mà n=9 đã > 2 tỷ rồi

1 1
2 1
3 2
4 8
5 86
6 1770
7 88418
8 8934966
9 2087813834
10 1013346943033
11 1111598871478668
12 2568944901392936854
13 13251059359839620127088
14 145194816279817259193401518
15 3524171261632305641165676374930
16 182653259988707123426135593460533473
17 20867537601324146829127267814319046730462
18 5108466695838037792668155733045329910045302167