当前位置:网站首页>【暑期每日一题】洛谷 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;
}
边栏推荐
猜你喜欢
自动化测试-图片中添加文字注释,添加到allure测试报告中
2022R1快开门式压力容器操作考试模拟100题及在线模拟考试
2022 High Voltage Electrician Exam Questions and Answers
Polygon zkEVM Prover
ceph创建存储池,映射,删除练习
关于sys.path.append(‘..‘)失效
单根k线图知识别以为自己都懂了
MySQL:已提交读和可重复读的实现原理 | MVCC(多版本并发控制)——笔记自用
2022 High-altitude installation, maintenance, and demolition exam practice questions and mock exams
使用Oracle SQL Developer管理Oracle Database Express Edition (XE)
随机推荐
AttributeError: partially initialized module ‘cv2‘ has no attribute ‘gapi_wip_gst_GStreamerPipeline‘
gopacket使用示例
杰理之一拖二 另一台手机超距 通话会无声【篇】
npm package.json
AttributeError: partially initialized module 'cv2' has no attribute 'gapi_wip_gst_GStreamerPipeline'
杰理之播放最大音量提示音播不出来【篇】
【服务器数据恢复】Ext4文件系统fsck后mount不上并报错的数据修复案例
“error“: { “root_cause“: [{ “type“: “circuit_breaking_exception“, “reason“: “[parent] D [solved]
阿里云天池大赛赛题(机器学习)——天猫用户重复购买预测(完整代码)
[math] dot product and cross product
Alibaba Cloud Tianchi Contest Question (Machine Learning) - Repeat Purchase Prediction of Tmall Users (Complete Code)
Flask框架实现异步处理请求
I.MX6U-ALPHA开发板(串口实验)
阿里云天池大赛赛题(深度学习)——视频增强(完整代码)
Ali YunTianChi competition problem (deep learning) - video enhancement (complete code)
761. 特殊的二进制序列(分治)
MySQL:已提交读和可重复读的实现原理 | MVCC(多版本并发控制)——笔记自用
TCP/IP协议中分包与重组原理介绍、分片偏移量的计算方法、IPv4报文格式
2022 High Voltage Electrician Exam Questions and Answers
y91.第六章 微服务、服务网格及Envoy实战 -- 服务网格基础(二)