4130: 帕斯卡的旅行(tour)

Memory Limit:128 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:12 Solved:7

Description

【问题描述】

在一个n×n个方格的游戏板中,每个方格中有一个非负整数。游戏的目标是从游戏板的左上角沿任何合法路径移动到右下角。任何一个方格内的数字规定了离开本方格的一步必须移动的方格数。如果移动的一步越出了游戏板,则这个方向的移动是禁止的。每一步移动只能是向下或向右的。考虑如图1所示的4×4的板,这里黑体字表示出发位置,斜体字表示目的位置。图2显示了从出发位置到目的位置的三条路径,其中隐去了与每条路径无关的数字

 

【输入格式】 

n+1行,第一行是游戏板的行数n4<=n<=34),接下来是n个数据行,每行含有n09的数字,中间没有空格。

【输出格式】

在一行中输出从左上角到右下角的路径数。(输出结果保证小于2^63

输入输出样例:

 

输入

输出

样例1

4

2331

1213

1231

3110

3

样例2

4

3332

1213

1232

2120

0

样例3

5

11111

11111

11111

11111

11111

70

加入题单

上一题 下一题 算法标签: