P4734 路径计数（基础）

解题思路

有一个 N×N 的网格，我们从左上角 (1,1) 出发，每次只能向下或向右走一格，要走到右下角 (N,N)。网格里有 M 个格子是障碍，不能经过。问一共有多少种不同的走法。

我们用"动态规划"来数路线。设 dp[i][j] 表示从起点走到 (i,j) 这个格子的走法数。起点格子 (1,1) 只有 1 条路，dp[1][1]=1。对于任意一个格子，到达它的方式只有两种：从它上方的格子 (i-1,j) 向下走一步，或者从它左边的格子 (i,j-1) 向右走一步。所以 dp[i][j] = dp[i-1][j] + dp[i][j-1]。如果 (i,j) 本身是障碍，那它一条路都没有，dp[i][j]=0。我们按行从上到下、每行从左到右逐个格子计算，最后 dp[N][N] 就是答案。

做这道题要注意三点：第一，障碍坐标可能重复出现，用 bool 数组标记，同一个格子只标一次；第二，路径数量可能非常大，比如 20×20 没有障碍时约有 350 亿条，超过 int 的范围，所以用 long long 存；第三，题目保证起点和终点没有障碍，而且起点到终点至少有一条通路。以样例为例，N=3 时只有 (3,1) 一个障碍，从 (1,1) 到 (3,3) 一共有 5 种走法，与输出一致。

参考代码

// 路径计数：N*N网格从左上角(1,1)走到右下角(N,N)，只能下移或右移，统计经过障碍的路径数
#include <iostream>
int main(){
  long long dp[25][25];
  bool block[25][25]={false};  // 记录障碍格子
  int n,m,i,j,x,y;
  std::cin>>n>>m;
  for(i=0;i<m;i++){            // 读入m个障碍
    std::cin>>x>>y;
    block[x][y]=true;          // 相同坐标的障碍只标记一次
  }
  dp[1][1]=1;                  // 起点有1条路
  for(i=1;i<=n;i++){
    for(j=1;j<=n;j++){
      if(i==1&&j==1) continue;
      if(block[i][j]){ dp[i][j]=0; continue; }  // 障碍格路径数为0
      dp[i][j]=0;
      if(i>1) dp[i][j]+=dp[i-1][j];             // 从上方格子下来
      if(j>1) dp[i][j]+=dp[i][j-1];             // 从左方格子过来
    }
  }
  std::cout<<dp[n][n];
  return 0;
}

复杂度分析

需要遍历 N×N 个格子，每个格子只做常数次加法，所以时间 O(N²)。空间上用一个 25×25 的 long long 数组和一个 bool 数组，是 O(N²)。N 最大 20，一共只有 400 个格子，完全没问题。