当前位置:网站首页>【暑期每日一题】洛谷 P1176 路径计数2
【暑期每日一题】洛谷 P1176 路径计数2
2022-08-09 04:32:00 【AC_Dragon】
题目链接:P1176 路径计数2 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目描述
一个 N × N 的网格,你一开始在 (1,1),即左上角。每次只能移动到下方相邻的格子或者右方相邻的格子,问到达 (N,N),即右下角有多少种方法。
但是这个问题太简单了,所以现在有 M 个格子上有障碍,即不能走到这 M 个格子上。
输入格式
输入文件第 1 行包含两个非负整数 N,M,表示了网格的边长与障碍数。
接下来 M 行,每行两个不大于 N 的正整数 x, y。表示坐标 (x, y) 上有障碍不能通过,且有 1≤x, y≤n,且 x, y 至少有一个大于 1,并请注意障碍坐标有可能相同。
输出格式
一个非负整数,为答案 mod 100003 后的结果。
样例 #1
样例输入 #1
3 1
3 1
样例输出 #1
5
提示
对于 20% 的数据,有 N≤3;
对于 40% 的数据,有 N≤100;
对于 40% 的数据,有 M=0;
对于 100% 的数据,有 N≤1000,M≤100000。
AC code:
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int a[N][N];
int f[N][N]; // f[x][y]表示从(1,1)到达(x,y)的方案总数
int main()
{
int n,m;
cin>>n>>m;
while(m--)
{
int x,y;
cin>>x>>y;
a[x][y]=1;
}
f[1][1]=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
if(a[i][j]==0 && !(i==1 && j==1))
{
f[i][j]=(f[i-1][j]+f[i][j-1])%100003;
}
}
cout<<f[n][n];
return 0;
}
边栏推荐
猜你喜欢
软件质效领航者 | 优秀案例•国金证券DevOps建设项目
ABP中的数据过滤器
Construction and practice of full stack code test coverage and use case discovery system
松柏集(浮窗思)
JVM垃圾回收机制简介
ceph创建存储池,映射,删除练习
2022 Security Officer-A Certificate Special Work Permit Exam Question Bank and Online Mock Exam
2022年安全员-B证考试练习题及在线模拟考试
2022高压电工考试试题及答案
杰理之开关降噪语音识别没有用【篇】
随机推荐
安装pytorch和cuda
查询某时间段获得的积分总积分的大小进行排序
2022-08-07 反思
Improve the user experience and add a small detail to your modal popup
MySql.Data.MySqlClient.DBNull
基因对疾病的影响规律--读论文
配置网络接口的“IP“命令
[math] dot product and cross product
消失的遗传力--wiki
MySQL:意向共享锁和意向排它锁 | 死锁 | 锁的优化
Gopacket source code analysis
Win11一键重装系统后如何使用自带的故障检测修复功能
360 评估反馈问题的示范案例
OKR management process, how to implement effective dialogue, using the CFR feedback and recognition?
阿里云天池大赛赛题(机器学习)——工业蒸汽量预测(完整代码)
pytorch implementation of Poly1CrossEntropyLoss
ceph创建存储池,映射,删除练习
Device Reliability vs. Temperature
2022 High-altitude installation, maintenance, and demolition exam practice questions and mock exams
simple math formula calculation