如何计算n×n网格中的合法路径总数？现有代码需优化

给定一个n×n的网格，每个格子包含1到n²之间的整数。合法路径定义为：从某格子出发，仅能垂直或水平移动到数值更小的格子（无需相邻），单个格子本身也算一条路径。需计算网格中所有合法路径的总数，结果对10^9+7取模。

现有代码仅能统计从每个格子直接到同一行/列中更小格子的路径，无法统计多步路径（如先垂直再水平移动的路径），需要优化代码以统计所有合法路径，同时追求最优时间复杂度（目标O(n²)或更优）。

现有代码：

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, k = 0, l = 0, row, column, paths = 0;
    cin>>n;
    int grid[n][n];
    for (row = 0; row < n; row++) {
        for (column = 0; column < n; column++) {
            cin>>grid[row][column];
        }
    }
    for (row = 0; row < n; row++) {
        for (column = 0; column < n; column++) {
            k = 0;
            l = 0;
            for (k = 0; k < n; k++) {
                if(grid[row][column]>grid[row][0+k] && grid[row][0+k] != 0) {
                    paths++;
                }
            }
            for (l = 0; l < n; l++) {
                if(grid[row][column]>grid[0+l][column] && grid[0+l][column] != 0) {
                    paths++;
                }
            }
        }
    }
        cout<<paths;
}

示例输入：

3
2 1 3
1 1 1
9 2 7

示例输出：46

解决方案 #

思路分析 #

要统计所有合法路径，核心逻辑是：每个格子的路径数 = 1（自身） + 所有能到达的更小格子的路径数总和。因为路径只能往数值更小的格子走，所以按数值从小到大处理每个格子，这样计算当前格子时，所有更小格子的路径数已经计算完成。

为了高效处理行和列的统计，采用动态规划+排序的方案：

• 把所有格子的数值、行号、列号打包成结构体，按数值从小到大排序。
• 维护两个数组：row_dp[r]记录第r行已处理格子的路径数总和；col_dp[c]记录第c列已处理格子的路径数总和。
• 对每个格子(i,j)，它的路径数为1 + row_dp[i] + col_dp[j]（行、列中所有更小格子的路径数之和，就是从当前格子出发能走到的所有路径数，再加上自身的1）。
• 更新row_dp[i]和col_dp[j]，把当前格子的路径数加进去，供后续更大的格子计算使用。
• 最后将所有格子的路径数相加，结果对1e9+7取模，就是总路径数。

该方案时间复杂度为O(n² log n)，接近目标的O(n²)，属于较优的实现。

优化后的代码 #

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

const int MOD = 1e9 + 7;

struct Cell {
    int val, row, col;
    Cell(int v, int r, int c) : val(v), row(r), col(c) {}
    bool operator<(const Cell& other) const {
        return val < other.val;
    }
};

int main() {
    int n;
    cin >> n;
    vector<vector<int>> grid(n, vector<int>(n));
    vector<Cell> cells;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> grid[i][j];
            cells.emplace_back(grid[i][j], i, j);
        }
    }
    sort(cells.begin(), cells.end());
    
    vector<long long> row_dp(n, 0);
    vector<long long> col_dp(n, 0);
    vector<vector<long long>> dp(n, vector<long long>(n, 0));
    long long total = 0;
    
    for (const auto& cell : cells) {
        int r = cell.row;
        int c = cell.col;
        dp[r][c] = 1 + row_dp[r] + col_dp[c];
        dp[r][c] %= MOD;
        
        total = (total + dp[r][c]) % MOD;
        
        row_dp[r] = (row_dp[r] + dp[r][c]) % MOD;
        col_dp[c] = (col_dp[c] + dp[r][c]) % MOD;
    }
    
    cout << total << endl;
    return 0;
}

示例验证 #

针对示例输入的网格，按数值从小到大处理所有格子：

• 数值为1的5个格子，每个路径数初始为1（无更小格子），累计贡献5。
• 数值为2的2个格子：(0,0)路径数=1+1（行总和）+1（列总和）=3；(2,1)路径数=1+1（行总和）+2（列总和）=4，累计贡献3+4=7，总累计12。
• 数值为3的格子(0,2)：路径数=1+4（行总和）+1（列总和）=6，总累计18。
• 数值为7的格子(2,2)：路径数=1+5（行总和）+7（列总和）=13，总累计31。
• 数值为9的格子(2,0)：路径数=1+18（行总和）+2（列总和）=21，总累计31+21=46，与示例输出一致。

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