蜗牛爬行

题目描述:

      在一个n*n的矩阵中，每个矩形里都有一个大于等于0，小于等于9的数。一只蜗牛想从这个矩阵的左上角开始爬行，可以向下或向右走。这只蜗牛很喜欢收藏数字，他要求他经过0~9的所有数字，这样他就可以收藏他们。但是，他也要求他走过的矩形中的数字之和最小。请你帮他求出数值。

输入格式:

      第一行一个整数n(n<=12)，表示矩阵大小。

      第二行到底n+1行，每行n个整数，为0~9之中的数。表示矩阵中每个矩形的数字。

输出格式:

      共一行，表示这只蜗牛最小爬过的数字总和。若他无法爬过所有0~9的数字，输出"LJC AK IOI!!!"（不输出引号）（数据太fake了）。

样例输入:

10
0 1 2 3 4 5 6 7 8 9
1 1 1 1 1 1 1 1 1 0
2 1 1 1 1 1 1 1 1 0
3 1 1 1 1 1 1 1 1 0
4 1 1 1 1 1 1 1 1 0
5 1 1 1 1 1 1 1 1 0
6 1 1 1 1 1 1 1 1 0
7 1 1 1 1 1 1 1 1 0
8 1 1 1 1 1 1 1 1 0
9 1 1 1 1 1 1 1 1 5

样例输出:

50

提示:

      对于30%的数据，n<=7；

      对于60%的数据，n<=10；

      对于100%的数据，n<=12.

      样例解释（如下，走红色路径最优）：

0 1 2 3 4 5 6 7 8 9
1 1 1 1 1 1 1 1 1 0
2 1 1 1 1 1 1 1 1 0
3 1 1 1 1 1 1 1 1 0
4 1 1 1 1 1 1 1 1 0
5 1 1 1 1 1 1 1 1 0
6 1 1 1 1 1 1 1 1 0
7 1 1 1 1 1 1 1 1 0
8 1 1 1 1 1 1 1 1 0
9 1 1 1 1 1 1 1 1 5

      本题数据由zhr1502生成，未经允许，不得纂改！！

时间限制: 1000ms
空间限制: 256MB

---

来源: by zhr