题意分析

奶牛们在 $N \times N$ 的棋盘上进行“跳牛”游戏，棋盘上的每个格子有一个唯一的数字（$1$ 到 $N \times N$）。奶牛从某个格子出发，按照国际象棋中“马”的走法（即“日”字形移动）跳到数字更大的格子，直到无法移动为止。目标是找到一条最长的路径（得分最高），如果有多条路径得分相同，则选择字典序最小的路径。

解题思路

1. 动态规划与记忆化搜索：

   • 定义 $dp[i][j]$ 表示从格子 $(i, j)$ 出发能走的最长路径长度。
   • 对于每个格子 $(i, j)$，检查其 8 个可能的“马”跳方向，如果目标格子的数字更大，则递归计算目标格子的 $dp$ 值，并选择其中最大的 $dp$ 值加 1 作为当前格子的 $dp$ 值。
   • 同时记录路径的下一步格子，以便后续输出路径。

2. 字典序处理：

   • 在动态规划过程中，如果多个方向能提供相同长度的路径，选择数字最小的格子作为下一步，以确保路径的字典序最小。

3. 时间复杂度：

   • 每个格子最多被处理一次，每次处理需要检查 8 个方向，因此总时间复杂度为 $O(N^2)$。

标程

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define debug 0
#define MAXN 400
#define INF 0x3f3f3f3f

struct node {
	int ways;
	int i, j;
} dp[MAXN][MAXN];

int maps[MAXN][MAXN] = {0};
int N;
const int dirx[8] = {-2, -1, 1, 2, 1, 2, -1, -2};
const int diry[8] = {-1, -2, -2, -1, 2, 1, 2, 1};

int bfs(int x, int y) {
	if (dp[x][y].ways)
		return dp[x][y].ways;
	
	int maxs = 0;
	int maxx = N, maxy = N;
	
	for (int i = 0; i < 8; i++) {
		int x0 = x + dirx[i];
		int y0 = y + diry[i];
		
		if (x0 >= 0 && y0 >= 0 && x0 < N && y0 < N && maps[x0][y0] > maps[x][y]) {
			int current = bfs(x0, y0);
			if (maxs < current || (maxs == current && maps[x0][y0] < maps[maxx][maxy])) {
				maxs = current;
				maxx = x0;
				maxy = y0;
			}
		}
	}
	
	dp[x][y].ways = maxs + 1;
	if (maxs > 0) {
		dp[x][y].i = maxx;
		dp[x][y].j = maxy;
	}
	
	return dp[x][y].ways;
}

int main() {
#if debug
#endif
	
	cin.tie(0);
	cin.sync_with_stdio(false);
	
	while (cin >> N) {
		maps[N][N] = INF;
		

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				cin >> maps[i][j];
				dp[i][j].ways = 0;
				dp[i][j].i = -1;
				dp[i][j].j = -1;
			}
		}
		

		int maxs = 0;
		int maxi = 0, maxj = 0;
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				bfs(i, j);
				if (maxs < dp[i][j].ways || 
					(maxs == dp[i][j].ways && maps[i][j] < maps[maxi][maxj])) {
					maxs = dp[i][j].ways;
					maxi = i;
					maxj = j;
				}
			}
		}

		cout << maxs << endl;
		while (maxi != -1) {
			cout << maps[maxi][maxj] << endl;
			int a = maxi, b = maxj;
			maxi = dp[a][b].i;
			maxj = dp[a][b].j;
		}
	}
	
	return 0;
}