当前位置:首页 > 动态规划 > 二维DP > 正文
洛谷P1176路径计数2
2343+

题目大意:n*n的棋盘,只能向右走或者向下走,每次只能走一个格子,遇到障碍物不能走,从(1,1)走到(n,n)共有多少种走法?

题目描述

一个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:

3 1
3 1
输出样例#1:

5

说明

对于20%的数据,有N≤3;

对于40%的数据,有N≤100;

对于40%的数据,有M=0;

对于100%的数据,有N≤1000,M≤100000。

解题思路

用二维数组记录地图,不能走标记为-1。从上到下、从左到右枚举给个格子,用已知的格子推出未知的格子的方案数。如果没有障碍物,当前格子的方案数等于上方格子方案数加上左边格子的方案数,有障碍物的格子不用加且不计算方案数。

程序实现

About

坚决不Copy代码!

本文标签:,,,,

洛谷P1176路径计数2:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!