1732: 棋盘格取数和最大
Memory Limit：128 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：72
Solved：10
Description
给你一个n*n格子的棋盘，每个格子里面有一个非负数。请你从中取出若干个数，取出的任意两个数所在的格子不能相邻，并且取出数的和最大。
注意，棋盘格子上下左右为相邻的格子。
Input
输入第一行为一个整数 n。第二行起为n*n个非负数(n<=18)。
Output
输出可能取得的最大的和。
Sample Input Copy
3
1 2 3
4 5 6
7 8 9
Sample Output Copy
25
HINT
1=<n<=18 (方格中的数<1000)