题目描述
一个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后的结果。
输入输出样例
说明
对于20%的数据，有N≤3；
对于40%的数据，有N≤100；
对于40%的数据，有M=0；
对于100%的数据，有N≤1000,M≤100000。
这道题是不是过水叻QAQ不过挂上来以后也可以看看嘛...
就是直接$n^2$递推转移即可...
#include<iostream> #include<cstdio> #define MOD 100003 using namespace std; int n, m; int dp[1005][1005], flag[1005][1005]; int main ( ) { scanf ( "%d%d", &n, &m ); for ( int i = 1; i <= m; i ++ ) { int x, y; scanf ( "%d%d", &x, &y ); flag[x][y] = 1; } dp[1][1] = 1; for ( int i = 1; i <= n; i ++ ) for ( int j = 1; j <= n; j ++ ) { if ( !flag[i+1][j] ) dp[i+1][j] = ( dp[i+1][j] + dp[i][j] ) % MOD; if ( !flag[i][j+1] ) dp[i][j+1] = ( dp[i][j] + dp[i][j+1] ) % MOD; } printf ( "%d", dp[n][n] ); return 0; }