矩阵中全访问路径计数的回溯法实现及剪枝优化问询

问题描述 #

给定M×N矩阵，需计算从左上角单元格(0,0)到右下角单元格(M-1,N-1)的有效路径总数。有效路径要求每个单元格仅被访问一次，允许上、下、左、右移动。已基于回溯法实现初步代码，包含边界、提前到达终点等剪枝条件，但无法实现「路径将矩阵分割为两个未访问区域」的剪枝判断，寻求实现建议与优化方案。

现有代码 #

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
/*
    N*M matrix
    0<=x<M
    0<=y<N
*/

void CountPaths(int x, int y, int M, int N, ll &paths, vector<vector<bool>> &grid, int k)
{ 
    if (x == M-1 && y == N-1 && k == N*M){
        paths++;
        return;
    } // 有效路径计数

    if (x < 0 || y < 0 || x >= M || y >= N || grid[y][x] == true) {
        return;
    } // 越界或已访问，剪枝

    if(x == M-1 && y == N-1 && k!=M*N) return; // 提前到达终点但未遍历所有单元格，剪枝
    if (y == N-1 && 0<x && x<M-1 && !grid[y][x-1] && !grid[y][x+1]) return; // 边界行中间单元格被孤立，剪枝
    if (x == M-1 && 0<y && y<N-1 && !grid[y-1][x] && !grid[y+1][x]) return; // 边界列中间单元格被孤立，剪枝
    if (y == 0 && 0<x && x<M-1 && !grid[y][x-1] && !grid[y][x+1]) return; // 首行中间单元格被孤立，剪枝
    if (x == 0 && 0<y && y<N-1 && !grid[y-1][x] && !grid[y+1][x]) return; // 首列中间单元格被孤立，剪枝

    grid[y][x] = 1;
    CountPaths(x + 1, y, N, M, paths, grid, k + 1); // 右
    CountPaths(x, y + 1, N, M, paths, grid, k + 1); // 下
    CountPaths(x - 1, y, N, M, paths, grid, k + 1); // 左
    CountPaths(x, y - 1, N, M, paths, grid, k + 1); // 上
    grid[y][x] = 0; // 回溯
}

int main(void){
    int N = 9; // 行数
    int M = 9; // 列数
    vector<vector<bool>> grid(N, vector<bool>(M, false));
    ll paths = 0;
    CountPaths(0, 0, M, N, paths, grid, 1);

    cout << "Number of paths in a " << N << "x" << M << " matrix: " << paths << endl;
    return 0;
}

优化方案与剪枝实现 #

1. 核心剪枝：路径分割未访问区域的判断 #

当当前路径将未访问的单元格分割为两个不连通区域，且其中一个区域不包含终点时，后续不可能遍历完所有单元格，可直接剪枝。实现步骤：

• 编写辅助函数isConnected，传入当前网格状态、矩阵尺寸，判断未访问区域是否连通且包含终点：
  1. 统计未访问单元格的总数totalUnvisited；
  2. 若终点已被访问，只需判断剩余未访问单元格是否连通；
  3. 若终点未被访问，从终点出发做DFS/BFS，统计可达的未访问单元格数量reachable；
  4. 若reachable != totalUnvisited，说明未访问区域被分割，返回false。
• 在回溯函数中，标记当前单元格为已访问后，调用isConnected，若返回false则直接回溯，不继续递归。

2. 其他优化点 #

• 方向优先级调整：优先递归靠近终点的方向（右、下），可更早触发剪枝，减少无效递归次数；
• 对称性剪枝：若矩阵为正方形（M=N），可利用矩阵的对称性（上下/左右翻转），计算四分之一的路径数再乘以对应倍数（注意路径经过对称轴时的去重）；
• 位压缩存储：对于小尺寸矩阵（如M×N ≤ 64），用64位整数代替二维数组存储访问状态，每个位对应一个单元格的访问情况，大幅提高状态判断效率。

带分割剪枝的代码示例 #

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;

// 判断未访问区域是否连通且能到达终点（若终点未被访问）
bool isConnected(int M, int N, const vector<vector<bool>>& grid) {
    int totalUnvisited = 0;
    // 统计未访问单元格总数
    for (int y = 0; y < N; ++y) {
        for (int x = 0; x < M; ++x) {
            if (!grid[y][x]) totalUnvisited++;
        }
    }
    if (totalUnvisited == 0) return true;

    // 若终点已被访问，判断剩余未访问区域是否连通
    if (grid[N-1][M-1]) {
        // 找第一个未访问单元格作为起点
        int startX = -1, startY = -1;
        for (int y = 0; y < N; ++y) {
            for (int x = 0; x < M; ++x) {
                if (!grid[y][x]) {
                    startX = x;
                    startY = y;
                    break;
                }
            }
            if (startX != -1) break;
        }
        // BFS遍历连通区域
        vector<vector<bool>> visited = grid;
        queue<pair<int, int>> q;
        q.push({startX, startY});
        visited[startY][startX] = true;
        int count = 1;
        int dx[] = {0, 0, 1, -1};
        int dy[] = {1, -1, 0, 0};
        while (!q.empty()) {
            auto [x, y] = q.front();
            q.pop();
            for (int i = 0; i < 4; ++i) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx >=0 && nx < M && ny >=0 && ny < N && !visited[ny][nx]) {
                    visited[ny][nx] = true;
                    count++;
                    q.push({nx, ny});
                }
            }
        }
        return count == totalUnvisited;
    } else {
        // 从终点出发遍历未访问区域
        vector<vector<bool>> visited = grid;
        queue<pair<int, int>> q;
        q.push({M-1, N-1});
        visited[N-1][M-1] = true;
        int count = 1;
        int dx[] = {0, 0, 1, -1};
        int dy[] = {1, -1, 0, 0};
        while (!q.empty()) {
            auto [x, y] = q.front();
            q.pop();
            for (int i = 0; i < 4; ++i) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx >=0 && nx < M && ny >=0 && ny < N && !visited[ny][nx]) {
                    visited[ny][nx] = true;
                    count++;
                    q.push({nx, ny});
                }
            }
        }
        return count == totalUnvisited;
    }
}

void CountPaths(int x, int y, int M, int N, ll &paths, vector<vector<bool>> &grid, int k)
{ 
    if (x == M-1 && y == N-1 && k == N*M){
        paths++;
        return;
    }

    if (x < 0 || y < 0 || x >= M || y >= N || grid[y][x] == true) {
        return;
    }

    if(x == M-1 && y == N-1 && k!=M*N) return;
    if (y == N-1 && 0<x && x<M-1 && !grid[y][x-1] && !grid[y][x+1]) return;
    if (x == M-1 && 0<y && y<N-1 && !grid[y-1][x] && !grid[y+1][x]) return;
    if (y == 0 && 0<x && x<M-1 && !grid[y][x-1] && !grid[y][x+1]) return;
    if (x == 0 && 0<y && y<N-1 && !grid[y-1][x] && !grid[y+1][x]) return;

    grid[y][x] = 1;
    // 添加分割区域剪枝
    if (isConnected(M, N, grid)) {
        CountPaths(x + 1, y, M, N, paths, grid, k + 1);
        CountPaths(x, y + 1, M, N, paths, grid, k + 1);
        CountPaths(x - 1, y, M, N, paths, grid, k + 1);
        CountPaths(x, y - 1, M, N, paths, grid, k + 1);
    }
    grid[y][x] = 0;
}

int main(void){
    int N = 5; // 行数
    int M = 5; // 列数
    vector<vector<bool>> grid(N, vector<bool>(M, false));
    ll paths = 0;
    CountPaths(0, 0, M, N, paths, grid, 1);

    cout << "Number of paths in a " << N << "x" << M << " matrix: " << paths << endl;
    return 0;
}

内容的提问来源于stack exchange，提问作者BeeP