6754 路径计数

#include<bits/stdc++.h>
using namespace std;

/*
用一个n行m列的二维数组，记录每个的路线 
第一行第一列 每个点的路线都是1 
之外所有的点的路线数量  = 上方+左方 
*/ 
long long a[21][21]; //a[i][j]代表到达i行j列的路线数量 
bool vis[21][21]; // 标记数组， vis[i][j]==0代表不是障碍物，1代表是障碍物 
int n,m; // n行n列    m个障碍物 

int main(){
	cin>>n>>m;
	
	//初始化第一行的位置，每个都是1
	for(int i=1;i<=n;i++){
		a[1][i] = 1;
	} 
	//初始化第一列的位置，每个都是1
	for(int i=1;i<=n;i++){
		a[i][1] = 1;
	} 
	
	//m个障碍物，障碍物位置标记成1
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		a[x][y] = 0;//障碍物没有路线 
		vis[x][y] = 1;
	} 
	
	
	//从2行2列的位置开始推导
	//状态转移公式：a[i][j]= a[i-1][j]  + a[i][j-1]
	for(int i=2;i<=n;i++){
		for(int j=2;j<=n;j++){
			if(vis[i][j] == 1){ //跳过障碍物位置 
				continue;
			}  
			a[i][j] = a[i-1][j]  + a[i][j-1];
		}
	}
	//输出右下角的终点路线数量
	cout<<a[n][n]; 
	
	return 0;
}