1. 冰雪裂隙
题目ID：
5300必做题100分
时间限制：1000ms空间限制：524288kB
题目描述
\,\,\,\,\,\,\,\,\, 在一块n·m的巨大冰面上，有一些冰块是不稳定的。第i行第j列的冰块稳定度为 a[i][j]。
\,\,\,\,\,\,\,\,\, 一条冰雪裂隙定义为一条从第1行到第n行的冰块组合，每行各一个。并且满足每行所选的冰块在下一行所选冰块的八连通区域内。
\,\,\,\,\,\,\,\,\, 现在想请你选出稳定度最小的一条冰雪裂隙。稳定度相同时选尽可能靠右的冰块。尽可能靠右可以这样定义：从上到下把每行选取的冰块序号写出来之后，字典序尽可能大。
输入格式
\,\,\,\,\,\,\,\,\, 第一行一个整数T，表示数据组数。
\,\,\,\,\,\,\,\,\, 每组数据第一行两个整数n和m，接下来n行m列表示每块冰块的稳定度。
输出格式
\,\,\,\,\,\,\,\,\, 每组数据先输出是第几组数据（格式见样例），再输出最终裂隙的每一行选第几个冰块。
样例
Input 1
2
4 3
55 32 75
17 69 73
54 81 63
47 5 45
6 6
51 57 49 65 50 74
33 16 62 68 48 61
2 49 76 33 32 78
23 68 62 37 69 39
68 59 77 77 96 59
31 88 63 79 32 34
Output 1
Case 1
2 1 1 2
Case 2
3 2 1 1 2 1
样例解释
\,\,\,\,\,\,\,\,\, 对每个TestSample的解释（为什么这个input会得到这个output）
数据范围
\,\,\,\,\,\,\,\,\,0 < T ≤ 30,0 < m,n ≤ 100.
\,\,\,\,\,\,\,\,\, 题目明显是DP或记忆化dfs()，是从第一行的所有点出发，一直往下搜索与记忆。可以用f[i][j]来存储当前位置的最小稳定度。本蚂蚁认为最大的难点，在于状态转移方程，这也是我创建这个话题的目的。
\,\,\,\,\,\,\,\,\, 然后我吐槽一下，样例解释是不是直接套模板哪？！