题解

令 dp[i][j] 表示到达格子 $(i,j)$ 的路径数。若该格为障碍，值为 0；否则只能从上方或左方进入，所以 dp[i][j]=dp[i-1][j]+dp[i][j-1]。起点可通行时设为 1。按从上到下、从左到右计算，时间与空间复杂度均为 $O(nm)$。