搜狗：

思路：

搜索：一共搜（2n-2）步，每一步有四种走法。考虑不相交等条件可以剪去很多枝。

复杂度为O(4^n）

动态规划：

by:

详细算法思路：http://www.51nod.com/question/index.html#!questionId=657

s[k][i][j] = max(s[k-1][i-1][j-1],s[k-1][i-1][j],s[k-1][i][j-1],s[k-1][j][i])+map[i][k-i]+map[j][k-j];

复杂度为O(n^3)

#include 
    
     #define MAX(a,b) (a)>(b)?(a):(b)using namespace std;#define N 5int map[5][5]={	{2,0,8,0,2},	{0,0,0,0,0},	{0,3,2,0,0},	{0,10,0,0,0},	{2,0,8,0,2}};int sumMax=0;int p1x=0;int p1y=0;int p2x=0;int p2y=0;int curMax=0;/*编号系统为：0000011111222223333344444走1次：编号有：0,1走2次：编号有：0,1,2走5次：编号有：1,2,3,4走k次：编号有：l,l+1,l+2...,h-1 //low,high 的计算见code编号到map坐标的转换为：编号i，则对应map[i][k-i].dp方程为：s[k][i][j] = max(s[k-1][i-1][j-1],s[k-1][i-1][j],s[k-1][i][j-1],s[k-1][j][i])+map[i][k-i]+map[j][k-j];*/int dp(void){	int s[2*N-1][N][N];	s[0][0][0]=map[0][0];		for(int k=1;k<2*N-1;k++){		int h = k
     
      =0)						t= MAX(t, s[k-1][i-1][j-1]);					if( j
      
       =0&&j
       
        sumMax)			sumMax = curMax;		return;	}	if( !(p1x==0 && p1y==0) && !(p2x==N-1 && p2y==N-1))	{		if( p1x>= p2x && p1y >= p2y )			return;	}	//right right	if( p1x+1