标签：障碍物 vis int 路径 路线 计数 101 8524
#include<bits/stdc++.h>
using namespace std;
/*
用一个n行m列的二维数组，记录每个的路线
第一行第一列 每个点的路线都是1
之外所有的点的路线数量 = 上方+左方
*/
long long a[101][101]; //a[i][j]代表到达i行j列的路线数量
bool vis[101][101]; // 标记数组， 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];
a[i][j] %= 100003; //避免结果过大，按照题目要求mod 100003
}
}
//输出右下角的终点路线数量
cout<<a[n][n];
return 0;
}
/**
* @runId: 8030172
* @language: C++
* @author: liubolin
* @submitTime: 2024-10-26 09:43:32
*/
标签：障碍物,
vis,
int,
路径,
路线,
计数,
101,
8524
From： https://www.cnblogs.com/risnotl/p/18516233