Problem H: 散步

"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $16$ 正确数量 $15$
裁判形式 标准裁判/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
1
6