[1109] 最优对称路径
- 时间限制: 1000 ms 内存限制: 65535 K
- 问题描述
-
给一个n行n列的网格，每个格子里有一个1到9的数字。你需要从左上角走到右下角，其中每一步只能往上、下、左、右四个方向之一走到相邻格子，不能斜着走，也不能走出网格，但可以重复经过一个格子。为了美观，你经过的路径还必须关于“左下-右上”这条对角线对称。下图是一个6x6网格上的对称路径。
你的任务是统计所有合法路径中，数字之和最小的路径有多少条。
- 输入
-
输入最多包含25组测试数据。每组数据第一行为一个整数n（2<=n<=100）。以下n行每行包含n个1到9的数字，表示输入网格。输入结束标志为n=0。
- 输出
-
对于每组数据，输出合法路径中，数字之和最小的路径条数除以1,000,000,009的余数。
- 样例输入
-
2 1 1 1 1 3 1 1 1 1 1 1 2 1 1 0
- 样例输出
-
2 3
- 提示
-
无
- 来源
-
The Seventh Hunan Collegiate Programming Contest
- 操作
-
