lqdoj 2022tpb04

Code

#include <bits/stdc++.h>
using namespace std;
int main(){
	int n,m;
	cin >> n >> m;
	bool a[n+1][n+1];
	for (int i=1;i<=n;i++){
		for (int j=1;j<=n;j++) a[i][j]=true;
	}
	while (m>0){
		m--;
		int x,y;
		cin >> x >> y;
		a[x][y]=false;
	}
	long long dp[n+1][n+1];
	if (a[1][1] == true) dp[1][1]=1;
	
	for (int i=2;i<=n;i++){
		if (a[i][1] == true) dp[i][1]=dp[i-1][1];
		else dp[i][1]=0;
		if (a[1][i]==true) dp[1][i]=dp[1][i-1];
		else dp[1][i]=0;
	}
	
	for (int i=2;i<= n;i++){
		for (int j=2;j<= n;j++){
			if (a[i][j]==true){
				dp[i][j] = dp[i][j-1] + dp[i-1][j];
			} else dp[i][j]=0;
		}
	}
	
//	for (int i =1;i<= n;i++){
//		for (int j =1;j<= n;j++) {
//			cout << dp[i][j] << " ";
//		}
//		cout << "\n";
//	}
		
	cout << dp[n][n];
	
	return 0;
}