题意过于简单，这里不在累赘。
思路
对于大多数要求求，最多或最少，或者方案数的题都用DP（动态规划）解决。
因此考虑DP解决。
设 dpi,jdp_{i,j}dpi,j 为第 iii 行第 jjj 列不同的路径数
初始状态
第 111 行第 111 列，作为起始点一定有且只有一种路径（即刚开始）。也就是 dp1,1=1dp_{1,1} = 1dp1,1 =1。
很明显，第 111 行在第 111 个障碍物之前所有的路径数也一定为 111。也就是 dp1,j=1dp_{1,j} = 1dp1,j =1 其中 j∈[1,k)j \in [1,k)j∈[1,k)，kkk 为第 111 行第一个障碍物的位置。原因很简单，由于不能往上走，所以第 111 只能一直往左走才可能到达。
同样的，第 111 列在第 111 个障碍物前所有的路径数一定为 111。也就是 dpj,1=1dp_{j,1} = 1dpj,1 =1 其中 j∈[1,k)j \in [1,k)j∈[1,k)，kkk 为第 111 行列第一个障碍物的位置。
动态方程
首先，障碍物无法到达，因此障碍物处的所有路径数为 000，也就是 dpi,j=0dp_{i,j} = 0dpi,j =0，其中 i,ji,ji,j 是所有障碍物的行数以及列数。
对于非障碍物，有两种到达方法，从它的正上方到达，和它的左边到达，因此其路径数为正上方与左边的路径数之和。即 dpi,j=dpi−1,j+dpi,j−1dp_{i,j} = dp_{i - 1,j} + dp_{i , j- 1}dpi,j =dpi−1,j +dpi,j−1 其中 i,ji,ji,j 分别为大于1的所有非障碍物坐标。
因此我们得出代码：
AC CODE
