题目链接

思路
对N*N网格中所有点进行搜索（dfs），搜索过程中对每一步进行记忆化存储，即dp数组保存从当前点开始可获得的最高得分，若后面需要用到前面计算过的数据，直接读取dp数组即可。

• dp[i][j]表示从点(i,j)出发可获得的最高得分。

由于本题需要输出最小的路线，所以在搜索过程中要注意，得分相同的两条路要考虑所在点的数字大小。
路径的记录用结构体保存。
不要忘了比较得分相同的起点中，哪个点的数字最小！
代码：

#include <iostream>
#include <cstring>
using namespace std;
int farm[370][370]={0},dp[370][370];
int nxtx[8]={2,1,-1,-2,-2,-1,1,2};
int nxty[8]={1,2,2,1,-1,-2,-2,-1};
int n;
struct nextStep { int x, y; }node[370][370]; //存储后继结点坐标
int dfs(int x, int y)
{
    if(dp[x][y]!=0) return dp[x][y];
    int maximum = /*farm[x][y]*/ 1;
    int minx = x + nxtx[0], miny = y + nxty[0]; // 记录farm值最小的坐标
    for(int i=0 ; i<8 ; i++)
    {
        int tx = x + nxtx[i];
        int ty = y + nxty[i];
        if(tx<=n && tx>=1 && ty<=n && ty>=1 && farm[x][y] < farm[tx][ty])
        {
            //maximum = max(maximum , dfs(tx,ty)+1);
            if(maximum<dfs(tx,ty)+1)
            {
                maximum = dfs(tx,ty)+1;
                node[x][y].x = tx, node[x][y].y = ty;
                minx = tx, miny = ty;
            }
            //相同时选farm值最小的
            else if(maximum==dfs(tx,ty)+1 && farm[minx][miny] > farm[tx][ty])
            {
                node[x][y].x = tx, node[x][y].y = ty;
                minx = tx, miny = ty;
            }
        }
    }
    return dp[x][y] = maximum;
}
int main()
{
    ios::sync_with_stdio(false);
    int i, j;
    memset(node,0,sizeof(node));
    cin >> n;
    for(i=1 ; i<=n ; i++)
        for(j=1 ; j<=n ; j++)
            cin >> farm[i][j];
    int maxscore=0, max_x, max_y; //最高得分，即最终结果；最终结果的x,y坐标
    for(i=1 ; i<=n ; i++)
    {
        for(j=1 ; j<=n ; j++)
        {
            if(dp[i][j]!=0) continue;
            dp[i][j] = dfs(i,j); //每个起始点的得分赋给dp[i][j]
            //maxscore = max(maxscore , dp[i][j]);
            if(maxscore < dp[i][j])
            {
                maxscore = dp[i][j];
                max_x = i, max_y = j;
            }
            //相同时选farm值最小的
            else if(maxscore == dp[i][j] && farm[max_x][max_y]>farm[i][j])
                max_x = i, max_y = j;
        }
    }
    cout<<maxscore<<endl;
    for(int t=0 ; t<maxscore ; t++)
    {   //输出路径
        cout<<farm[max_x][max_y]<<endl;
        int tx = max_x, ty = max_y;
        max_x = node[tx][ty].x;
        max_y = node[tx][ty].y;
    }
    return 0;
}