2026-05-11：统计在矩形格子里移动的路径数目。用go语言，给定一个 n 行 m 列的网格 grid，其中每个格子是字符 ‘.‘ 或 ‘#‘： ‘.‘ 表示该位置可以走，‘#‘ 表示该位置被

2026-05-11：统计在矩形格子里移动的路径数目。用go语言，给定一个 n 行 m 列的网格 grid，其中每个格子是字符 ‘.’ 或 ‘#’：

‘.’ 表示该位置可以走，‘#’ 表示该位置被阻塞。

需要统计从底行到顶行的“不同路径”的数量，并满足所有移动规则：

路径的起点在最后一行（行号 n-1）的任意一个可走格子；

路径的终点在第一行（行号 0）的任意一个可走格子。

每一步移动必须满足：

1. 起点和终点都必须是可走格子（不能走到 '# 上）。

2. 两个格子之间的欧几里得距离不超过给定整数 d；距离定义为
   (r1−r2)2+(c1−c2)2\sqrt{(r1-r2)^2+(c1-c2)^2}(r1−r2)2+(c1−c2)2​

3. 移动只能满足行方向限制：要么仍在同一行移动，要么只能向上移动到上一行（从第 r 行到第 r-1 行）。

4. 不能连续两步都不变行。也就是：如果某一步是“仍在同一行”（并且这一步还不是终点），那么下一步必须转而进入上一行。

要求输出满足上述条件的路径总数；结果需要对 1000000007 取模后返回。

1 <= n == grid.length <= 750。

1 <= m == grid[i].length <= 750。

grid[i][j] 为 ‘.’ 或 ‘#’。

1 <= d <= 750。

输入: grid = [“…”,“#.”], d = 1

输出: 2

解释:

我们按顺序标记路径中访问的单元格，从 1 开始。两条路径分别是：

.2
#1

32
#1

我们可以从单元格 (1, 1) 移动到单元格 (0, 1)，因为欧几里得距离为(1−0)2+(1−1)2=1<=d\sqrt{(1-0)^2+(1-1)^2}=1<=d(1−0)2+(1−1)2​=1<=d。

但是，我们不能从单元格 (1, 1) 移动到单元格 (0, 0)，因为欧几里得距离为(1−0)2+(1−0)2=2>d\sqrt{(1-0)^2+(1-0)^2}=\sqrt{2}>d(1−0)2+(1−0)2​=2​>d。

题目来自力扣3797。

路径统计算法详细过程解析

一、先明确核心定义（理解算法基础）

1. 网格与移动规则回顾

• 网格：2行2列，行号0（顶行，终点行）、1（底行，起点行），列号0、1
  行0：[0,0]='.'，[0,1]='.'
  行1：[1,0]='#'，[1,1]='.'
• 移动约束：
  1. 只能同行移动或向上一行移动，不能向下
  2. 不能连续两步同行移动（非终点时）
  3. 欧几里得距离 ≤d
  4. 起点：底行任意可走格；终点：顶行任意可走格
  5. 阻塞格#不可走

2. 算法核心状态定义（代码中的关键变量）

代码用动态规划+前缀和优化，定义了两个核心状态：

1. f[j]：到达当前行第j列，且上一步是「向上移动」的路径总数（满足：上一步从下一行上来，无连续同行移动风险）
2. g[j]：到达当前行第j列，且上一步是「同行移动」的路径总数（满足：下一步必须向上走，不能再同行）
3. sumF：f数组的前缀和数组（快速计算区间内f的总和）
4. sum：f+g数组的前缀和数组（快速计算区间内f+g的总和）
5. 取模：所有计算对1e9+7取模，保证数值不溢出

二、分步骤计算全过程

步骤1：初始化准备

1. 确定网格列数m=2
2. 创建两个前缀和数组：sumF（长度3，下标0_{2）、`sum`（长度3，下标0}2），初始值全为0
3. 固定取模值mod=1e9+7

步骤2：遍历第一行（底行，i=1，代码中循环第一个元素）

这一行是所有路径的起点行，必须单独初始化：

1. 遍历该行每一列（j=0 和 j=1）：

   • j=0：格子是#（阻塞），sumF[1] = sumF[0] = 0（无路径）
   • j=1：格子是.（可走，起点），sumF[2] = sumF[1] + 1 = 1
     ✅ 含义：起点行只有[1,1]有1条初始路径（自身），对应状态f（第一步天然是向上移动的初始状态）

2. 计算sum数组（f+g前缀和）：

   • j=0：阻塞，sum[1] = sum[0] = 0
   • j=1：可走，区间求和后sum[2] = 1
     ✅ 含义：起点行总有效路径数为1

步骤3：遍历第二行（顶行，i=0，代码中循环第二个元素）

这一行是终点行，所有路径最终要到达这里，核心计算开始：

子步骤3.1：计算当前行的sumF数组（状态f的前缀和）

f[j]代表：从下一行（行1）向上移动到达 [0,j]的路径数
距离约束：向上移动时，行差=1，因此列差必须 ≤0（因为√(1²+列差²) ≤1 → 列差=0）
遍历每一列：

1. j=0：格子是.，可走
   • 从下一行能向上到这里的列：只有[1,0]，但该格阻塞
   • 因此sumF[1] = 0
2. j=1：格子是.，可走
   • 从下一行能向上到这里的列：[1,1]（有效路径数=1）
   • 因此sumF[2] = 0 + 1 = 1

子步骤3.2：计算当前行的sum数组（f+g的前缀和）

g[j]代表：在当前行（行0）同行移动到达 [0,j]的路径数
sum统计f+g的总和，包含两种路径：

1. 从下一行向上来的路径（f）
2. 在本行同行移动来的路径（g）
   遍历每一列：
3. j=0：格子是.，可走，累加后值为0
4. j=1：格子是.，可走
   • 包含：向上来的1条路径 + 同行移动来的1条路径
   • 最终sum[2] = 2

步骤4：输出最终结果

取sum数组最后一个值（总路径数），取模保证非负 → 结果为2，和题目样例一致。

三、核心计算逻辑总结

1. 逐行处理：从底行（起点）开始，向上逐行计算到顶行（终点）
2. 状态分离：把路径分为「上一步向上」和「上一步同行」两种，严格遵守「不能连续同行移动」的规则
3. 前缀和优化：
   • 不暴力枚举所有满足距离的格子（会超时）
   • 用前缀和数组O(1)计算区间路径和，快速统计所有符合距离约束的路径数
4. 阻塞格处理：遇到#直接继承前一个前缀和值，代表该格无任何路径

四、时间复杂度 & 额外空间复杂度

1. 总时间复杂度

• 网格行数：n，列数：m
• 算法遍历每一行，每行内遍历每一列两次（一次算sumF，一次算sum）
• 每次列遍历内的操作都是O(1)（前缀和区间计算）
• 总时间复杂度：O(n × m)
• 补充：n和m最大都是750，750×750=562500次操作，效率极高

2. 总额外空间复杂度

• 代码只创建了两个一维前缀和数组：sumF和sum
• 两个数组长度都是m+1，无其他二维数组、递归栈等额外空间
• 总额外空间复杂度：O(m)
• 补充：仅和列数相关，与行数无关，空间占用极小

总结

1. 计算过程：从底行初始化路径 → 向上逐行用动态规划统计路径 → 前缀和快速计算符合距离的路径 → 最终统计顶行总路径
2. 时间复杂度：O(n·m)（线性遍历网格，最优效率）
3. 空间复杂度：O(m)（仅用两个一维数组，极致省空间）

Go完整代码如下：

packagemainimport("fmt")funcnumberOfRoutes(grid[]string,dint)int{constmod=1_000_000_007m:=len(grid[0])sumF:=make([]int,m+1)sum:=make([]int,m+1)fori,row:=rangegrid{// f 的前缀和forj,ch:=rangerow{ifch=='#'{sumF[j+1]=sumF[j]}elseifi==0{// 第一行（起点）sumF[j+1]=sumF[j]+1// DP 初始值}else{sumF[j+1]=(sumF[j]+sum[min(j+d,m)]-sum[max(j-d+1,0)])%mod}}// f[j] + g[j] 的前缀和forj,ch:=rangerow{ifch=='#'{sum[j+1]=sum[j]}else{// -f[j] 和 +f[j] 抵消了sum[j+1]=(sum[j]+sumF[min(j+d+1,m)]-sumF[max(j-d,0)])%mod}}}return(sum[m]+mod)%mod// +mod 保证结果非负}funcmain(){grid:=[]string{"..","#."}d:=1result:=numberOfRoutes(grid,d)fmt.Println(result)}

Python完整代码如下：

# -*-coding:utf-8-*-MOD=1_000_000_007defnumberOfRoutes(grid,d):m=len(grid[0])sumF=[0]*(m+1)sum_arr=[0]*(m+1)fori,rowinenumerate(grid):# f 的前缀和forj,chinenumerate(row):ifch=='#':sumF[j+1]=sumF[j]elifi==0:# 第一行（起点）sumF[j+1]=sumF[j]+1# DP 初始值else:sumF[j+1]=(sumF[j]+sum_arr[min(j+d,m)]-sum_arr[max(j-d+1,0)])%MOD# f[j] + g[j] 的前缀和forj,chinenumerate(row):ifch=='#':sum_arr[j+1]=sum_arr[j]else:# -f[j] 和 +f[j] 抵消了sum_arr[j+1]=(sum_arr[j]+sumF[min(j+d+1,m)]-sumF[max(j-d,0)])%MODreturn(sum_arr[m]+MOD)%MOD# +mod 保证结果非负defmain():grid=["..","#."]d=1result=numberOfRoutes(grid,d)print(result)if__name__=="__main__":main()

C++完整代码如下：

#include<iostream>#include<vector>#include<string>#include<algorithm>usingnamespacestd;constintMOD=1'000'000'007;intnumberOfRoutes(vector<string>&grid,intd){intm=grid[0].size();vector<int>sumF(m+1,0);vector<int>sum(m+1,0);for(inti=0;i<grid.size();i++){string row=grid[i];// f 的前缀和for(intj=0;j<m;j++){charch=row[j];if(ch=='#'){sumF[j+1]=sumF[j];}elseif(i==0){// 第一行（起点）sumF[j+1]=sumF[j]+1;// DP 初始值}else{sumF[j+1]=(sumF[j]+sum[min(j+d,m)]-sum[max(j-d+1,0)])%MOD;}}// f[j] + g[j] 的前缀和for(intj=0;j<m;j++){charch=row[j];if(ch=='#'){sum[j+1]=sum[j];}else{// -f[j] 和 +f[j] 抵消了sum[j+1]=(sum[j]+sumF[min(j+d+1,m)]-sumF[max(j-d,0)])%MOD;}}}return(sum[m]+MOD)%MOD;// +mod 保证结果非负}intmain(){vector<string>grid={"..","#."};intd=1;intresult=numberOfRoutes(grid,d);cout<<result<<endl;return0;}