计算矩阵中的路径 - 回溯

Question

给定一个 M*N 矩阵，我想计算从左上角单元格 (0,0) 到右下单元格 (m-1, n-1) 的可能路径总数。可能的移动包括上、下、右和左。仅当路径恰好访问每个单元 c(i, j) 一次时，该路径才被视为有效。如果超出矩阵边界或遇到先前访问过的单元格，则递归将被切断。

if (x < 0 || y < 0 || x >= m || y >= n || grid[x][y] == 1) {
        return;
    }

为了限制递归次数，我想到了一些明显的改进：

• 如果在访问所有单元格之前到达最后一个单元格，则该路径将无效；
• 如果到达边界单元格，即（i，n-1）或（m-1，j）形式的单元格，并且紧邻上方和下方（或右侧和左侧）的单元格尚未被访问，那么就不可能形成有效的路径；
• 同样，如果遇到先前访问过的单元格并且可以选择向两个不同的方向移动，则该路径将无效（实际上，我们将矩阵划分为两个未访问过的单元格区域）

我正在努力实施

void CountPath(int x, int y, int n, int m)

在 C++ 中使用回溯，你能建议我一些继续的方法吗？

我的想法是维护一个布尔矩阵来表示网格，并且在每一步检查各种条件后，根据相应的运动（设置调用 CountPath 的单元格为 1)。

编辑：经过一些测试后，我想出了这段似乎有效的代码。在确定路径遇到将矩阵划分为两个具有未访问单元的区域的点的条件时，我仍然存在一些问题。 请注意，我在此实现中使用了大小为 N*M 的矩阵。

#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;
    } // correct path

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

    if(x == M-1 && y == N-1 && k!=M*N) return; // c(n-1, m-1) - some grid[i][j]=0
    if (y == N-1 && 0<x && x<M-1 && !grid[y][x-1] && !grid[y][x+1]) return; // c(n-1, j)
    if (x == M-1 && 0<y && y<N-1 && !grid[y-1][x] && !grid[y+1][x]) return; // c(i, m-1)
    if (y == 0 && 0<x && x<M-1 && !grid[y][x-1] && !grid[y][x+1]) return; // c(0, j)
    if (x == 0 && 0<y && y<N-1 && !grid[y-1][x] && !grid[y+1][x]) return; // c(i, 0)


    grid[y][x] = 1;
    CountPaths(x + 1, y, N, M, paths, grid, k + 1); // right
    CountPaths(x, y + 1, N, M, paths, grid, k + 1); // down
    CountPaths(x - 1, y, N, M, paths, grid, k + 1); // left
    CountPaths(x, y - 1, N, M, paths, grid, k + 1); // up
    grid[y][x] = 0; // backtracking
}



int main(void){

    int N = 9; // row
    int M = 9; // column
    vector<vector<bool>> grid(N, vector<bool>(M, false));
    ll paths = 0;
    CountPaths(0, 0, M, N, paths, grid, 1);

   //freopen("output.txt", "w", stdout);
    cout << "Number of paths in a " << N << "x" << M << " matrix: " << paths << endl;


    return 0;
}

Answer 1

我可以为您提供伪代码。这是一个简单的递归算法。

我展示的是方形

N*N

案例，您可以将其用于更通用的矩形案例。

Paths(n) = paths(n, [(0,0)])
paths(n, [p, ...ps])
  | p == (n-1, n-1) = 
      length(ps)==(n^2-1) ? 1 : 0
  | outside?(n, p) = 0
  | member?(p, ps) = 0
  | otherwise = sum [ 
      paths(n, [q, p, ...ps])
      FOR q IN fourDirections(p) ]