首页 >> 大全

15312:迷宫

2023-08-27 大全 33 作者:考证青年

题目

晚上,跑男们来了节目的最后一站:江苏省扬州中学,完成最后一项比赛:撕名牌。撕名牌的地点是一个由n*n房间组成的正方形,每个房间里都有一个数字,表示从这个房间可以通过地道向右或向下穿过几个房间。从左上角开始,如果谁能安全到达右下角就算胜利。

这里4*4的方格中每一格表示进入这个房间时,队员可以向右或向下穿过的房间数。

郑恺是奔跑小王子,当他拿到这张地图时,脸都变绿了,速度再快,进了迷宫一样的房间也是没办法啊,还好参加夏令营的小伙伴都在,你能帮帮他算出从左上角可以到达右下角的路径数目吗?

输入

第一行为一个整数n,表示棋盘的大小。

以下有n行,每行有n个数字(数字与数字之间有一个空格隔开),表示在相应的格子内,棋子可以向右或向下跳跃的格子数。

输出

输出共一行,包含一个数,表示从左上角可以到达右下角的路径数目。

样例输入Copy

4
2 3 3 1
1 2 1 3
1 2 3 1
3 1 1 0

样例输出Copy

3

提示

对于100%的数据,1≤n≤100。

代码

#include 
using namespace std;
int n,ans=0;
int a[105][105];
void dfs(int x,int y)
{if(x==n&&y==n){ans++;return ;}if(x>n||y>n) return ;if(a[x][y]<=0) return ;dfs(x,y+a[x][y]);dfs(x+a[x][y],y);//不会走重复路,无需标记
}
int main()
{cin>>n;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++) cin>>a[i][j];dfs(1,1);cout<

关于我们

最火推荐

小编推荐

联系我们


版权声明:本站内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容, 请发送邮件至 88@qq.com 举报,一经查实,本站将立刻删除。备案号:桂ICP备2021009421号
Powered By Z-BlogPHP.
复制成功
微信号:
我知道了