题目描述一个 N×N 的网格你一开始在 (1,1)即左上角。每次只能移动到下方相邻的格子或者右方相邻的格子问到达 (N,N)即右下角有多少种方法。但是这个问题太简单了所以现在有 M 个格子上有障碍即不能走到这 M 个格子上。输入格式输入文件第 1 行包含两个非负整数 N,M表示了网格的边长与障碍数。接下来 M 行每行两个不大于 N 的正整数 x,y。表示坐标 (x,y) 上有障碍不能通过且有 1≤x,y≤n且 x,y 至少有一个大于 1并请注意障碍坐标有可能相同。输出格式一个非负整数为答案 mod100003 后的结果。输入输出样例输入 #1复制3 13 1输出 #1复制5说明/提示对于 20% 的数据有N≤3对于 40% 的数据有N≤100对于 40% 的数据有M0对于 100% 的数据有N≤1000,M≤100000。给大家画个图吧—————| 1 | 1 | 1 |—————| 1 | 2 | 3 |—————| x | 2 | 5 |—————x为障碍画出来这题就很好理解了,这道题其实非常简单跟2002年【NOIP普及组】过河卒基本思路一样用递推的思想把不能走的地方标记一下。极品AC代码#includebits/stdc.husingnamespacestd;inta[1001][1001],b[1001][1001];intmain(){intn,m,x,y;cinnm;for(inti1;im;i){cinxy;b[x][y]1;}a[1][1]1;for(inti1;in;i){for(intj1;jn;j){a[i][j]a[i-1][j]a[i][j-1];if(b[i][j]1){a[i][j]0;}a[i][j]a[i][j]%100003;}}couta[n][n];return0;}OK,到此为止下课