Problem H: 散步
| Time Limit |
$1$ 秒/Second(s) |
Memory Limit |
$512$ 兆字节/Megabyte(s) |
| 提交总数 |
$15$ |
正确数量 |
$14$ |
"
| 裁判形式 |
标准裁判/Standard Judge |
我的状态 |
尚未尝试 |
| 难度 |
|
分类标签 |
图论 搜索 |
当前分类(单击移除)：
图论搜索
单击选择分类：
⑨每天吃完晚饭后都会从家出发到雾之湖及其周围去散步下，最终到达魔法森林的入口，并且尽可能尝试不同的路径。雾之湖及其周围可以抽象为一个矩形，划分为n*m块区域，⑨家为(1,1)，散步时⑨在某个区域会逗留一段时间，然后移动到东西南北相邻的其中一个格子(移动时间忽略不计)，经过若干次移动最终到达魔法森林(n,m)。因为是散步，所以起点和终点⑨都会逗留一段时间。⑨表示虽然是闲逛，但是也不能太浪费时间，还是得去终点(n,m)的，所以只有至少存在一条从B到终点的时间比从A到终点的所有路径所花费的时间更少时才可以从A到B。现在⑨想知道自己一共有多少种路径可以选择，因为⑨的智商只有⑨，她自己肯定没法算出来啦。你能帮帮⑨吗？
本体有多组数据。每组数据第一行为n,m(2<=n,m<=50) 接下来为n行m列的矩阵，表示在每个区域⑨逗留的时间t（0<=t<=1000）。
每组数据输出一行，表示路径总数（保证小于2^63）。
3 3
1 2 3
1 2 3
1 2 3
3 3
1 1 1
1 1 1
1 1 1