题目内容

在 $n*n$ 的网格中，牛牛家在第 $1$ 行第 $1$ 列（左上角），青牛小学在第 $n$ 行第 $n$ 列（右下角）。 牛牛从家里出发，每一步可以往下或往右走，最终走到青牛小学。 在网格中，有两个位置都有一个障碍物，牛牛不能走到这两个位置。 牛牛从家里走到青牛小学的方案数是多少？

输入描述

第一行一个整数 $n$，表示网格的大小。

第二行两个整数 $x_1,y_1$，表示第一个障碍物在第$x_1$行$y_1$列。

解题思路与方法

动态规划

我们令 dp[i][j] 表示从起点 (1,1) 到达格子 (i,j) 的方案数。因为只能向下或向右走，状态转移方程为：

dp[i][j] = 
如果 (i,j) 是障碍，dp[i][j]=0  
否则 dp[i][j]=(dp[i-1][j] + dp[i][j-1]) mod M

边界条件：