317006 - 方格取数

【题目描述】17.6 方格取数（num）HDU 1565 有一个n×n格子的棋盘，每个格子里面有一个非负数。 从中取出若干个数，使得任意的两个数所在的格子没有公共边，就是说所取的数所在的2个格子不能相邻，并且取出的数的和最大。

输入包括多个测试实例，每个测试实例包括一个整数n（n≤20）和n×n个非负数。

对于每个测试实例，输出可能取得的最大的和。