P9743 「KDOI-06-J」旅行

小 C 在 C 国旅行。 C 国有 $n\times m$ 个城市，可以看做 $n\times m$ 的网格。定义 $(i,j)$ 表示在网格中第 $i$ 行第 $j$ 列的城市。 该国有 $2$ 种交通系统： * 对于所有 $1\leq i

无

无

**【样例解释 #1】** 到 $(3,1)$ 的方案有： * 在 $(1,1)$ 购买 $1$ 张 L 公司的铁路票；乘坐 L 公司的铁路到 $(2,1)$；在 $(2,1)$ 购买 $1$ 张 L 公司的铁路票；乘坐 L 公司的铁路到 $(3,1)$。 到 $(2,2)$ 的方案有： * 在 $(1,1)$ 购买 $1$ 张 L 公司的铁路票；乘坐 L 公司的铁路到 $(2,1)$；在 $(2,1)$ 购买 $1$ 张 Z 公司的铁路票；乘坐 Z 公司的铁路到 $(2,2)$。 到 $(3,2)$ 的方案有： * 在 $(1,1)$ 购买 $1$ 张 Z 公司的铁路票；乘坐 Z 公司的铁路到 $(1,2)$；在 $(1,2)$ 购买 $2$ 张 L 公司的铁路票；乘坐 L 公司的铁路到 $(2,2)$；乘坐 L 公司的铁路到 $(3,2)$。 * 在 $(1,1)$ 购买 $1$ 张 L 公司的铁路票和 $1$ 张 Z 公司的铁路票；乘坐 Z 公司的铁路到 $(1,2)$；乘坐 L 公司的铁路到 $(2,2)$；在 $(2,2)$ 购买 $1$ 张 L 公司的铁路票；乘坐 L 公司的铁路到 $(3,2)$。 * 在 $(1,1)$ 购买 $1$ 张 L 公司的铁路票和 $1$ 张 Z 公司的铁路票；乘坐 L 公司的铁路到 $(2,1)$；乘坐 Z 公司的铁路到 $(2,2)$；在 $(2,2)$ 购买 $1$ 张 L 公司的铁路票；乘坐 L 公司的铁路到 $(3,2)$。 到 $(2,3)$ 的方案有： * 在 $(1,1)$ 购买 $1$ 张 L 公司的铁路票和 $2$ 张 Z 公司的铁路票。在此之后，有 $3$ 种方案可以从 $(1,1)$ 乘坐两公司的铁路到 $(2,3)$。 * 在 $(1,1)$ 购买 $1$ 张 Z 公司的铁路票；乘坐 Z 公司的铁路到 $(1,2)$；在 $(1,2)$ 购买 $1$ 张 L 公司的铁路票和 $1$ 张 Z 公司的铁路票。在此之后，有 $2$ 种方案可以从 $(1,2)$ 乘坐两公司的铁路到 $(2,3)$。 **【样例 #2】** 见选手目录下的 `travel/travel2.in` 与 `travel/travel2.ans`。这个样例满足测试点 $7\sim 8$ 的条件限制。 **【样例 #3】** 见选手目录下的 `travel/travel3.in` 与 `travel/travel3.ans`。这个样例满足测试点 $11$ 的条件限制。 **【数据范围】** 对于所有数据保证：$1\leq n,m\leq45$，$1\leq k,a_{i,j},b_{i,j}\leq90$。 | 测试点编号 | $n,m$ | $k$ | $a_{i,j}$ | $b_{i,j}$ | |:--:|:--:|:--:|:--:|:--:| | $1\sim3$ | $\leq3$ | $\leq5$ | $=1$ | $=1$ | | $4\sim6$ | $\leq10$ | $\leq10$ | $=1$ | $=40$ | | $7\sim8$ | $\leq40$ | $\leq30$ | $=1$ | $=45$ | | $9\sim10$ | $\leq15$ | $\leq15$ | $\leq15$ | $\leq15$ | | $11$ | $\leq15$ | $\leq30$ | $\leq30$ | $\leq30$ | | $12$ | $\leq20$ | $\leq40$ | $\leq40$ | $\leq40$ | | $13\sim15$ | $\leq25$ | $\leq50$ | $\leq50$ | $\leq50$ | | $16$ | $\leq30$ | $\leq60$ | $\leq60$ | $\leq60$ | | $17$ | $\leq35$ | $\leq70$ | $\leq70$ | $\leq70$ | | $18\sim19$ | $\leq40$ | $\leq80$ | $\leq80$ | $\leq80$ | | $20$ | $\leq45$ | $\leq90$ | $\leq90$ | $\leq90$ |