选数

题目描述:

给你一个N*N（ 3<=N<=15)个矩阵，要你选择若干个数（每个数的范围在[10,99]），使得最后所选的数总和最大。选数的规则是如果选了某个数，那么它的八个相邻方向的数都不能选。

输入格式:

输入若干行，每行若干个数字，每个数字之间有一个空格，表示一个矩阵。

输出格式:

输出一个整数，表示选出的数的和的最大值。 

样例输入:

5
71 24 95 56 54
85 50 74 94 28
92 96 23 71 10
23 61 31 30 46
64 33 32 95 89

样例输出:

572

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

---