首页 > 其他分享 >8524 路径计数2

8524 路径计数2

时间:2024-10-30 17:19:41浏览次数:1  
标签:障碍物 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

相关文章