Question

各位大哥大姐，能不能帮我看看这一道简单的c语言题目。

输入一个N*N的二维数组，所有的元素都是自然数从中取任意个数，使得任意两个数都不相邻（包括行和列），并且取出的所有数的和最大，
输出最大值。
例如 输入
75 15 21
75 15 28
34 70 5
则输出
188

最好不要回答代码，把算法说明白就可以了
谢谢啦
我可能没有说明白，输入的有可能是这样的
75 1 1
1 1 75
75 1 1
这样的话，分成的两部分和都不是最大的
就是说不能简单的分成两部分，
取的个数最多的组合和并不一定越大。

Answer 1

都是自然数的话那么就都是大于0的
我们要取出的和最大
那么在可行条件下取得越多越好
那可行条件就是

如果我取（1,1）这个75
那么我还可以取的是（1,3）21，（2,2）15，（3,1）34，（3,3）5
如果我不取（1,1）
我取（1,2）15
那么我还可以取的就是（2,1）75，（2,3）28，（3，2）70
也就是说我可以把矩阵分成两部分
看其中哪部分的和更大 我就取那部分

-----------------------------------

应该是我理解错楼主的意思了
按你补充的说法
这道题就要用到dp的思想（动态规划）
首先是肯定不能贪心的，也就是一直选最大的
1 1 1
1 1 75
1 75 100
这个例子就过不了
具体的dp就没有那么好说了
状态转移也不是几句话就能讲明白的
真的对不住了。。。。。。
楼主可以先去了解一下dp
说不定你自己都能解决了
我很看好你哦~ ^0^

Answer 2

可以用深搜做，遍历每个位置，如a[i][j]，则与其不相邻的点为a[i-1][j-1],a[i-1][j+1],a[i+1][j-1],a[i+1][j+1]共4个点，将其加入队列