本题我靠此方法已AC（记录）。我翻了所有题解，似乎都是分类讨论得出路径的，没看到和我相似的做法，我感觉这种分类讨论做法写起来有点麻烦。

对于本题，我的处理方法是这样的，我们模拟代入题目中的这个人，在满足题意的前提下，按优先度：左下>右下>左上>右上 移动。

求证：这样他的移动轨迹是最优解之一，且可以实现

• 当 $n$ 为偶数时，有且仅有 $\forall i \in (1,n)$ ，第 $i$ 行第 $n - i + 1$ 列的方格不被通过（通俗地讲，就是 $n*n$ 的方格的左上到右下的对角线不走）.

• 当 $n$ 为奇数时，所有格子都被通过.

代码如下（附解释）：

#include <bits/stdc++.h>
using namespace std;
int main() {
	int n;
	scanf("%d", &n);
	vector <vector <bool>> m(n + 1, vector <bool> (n + 1, 0));//m[i][j]是0则表示没有或将来要通过，是1则表示已通过或本最优解不通过该点
	int ans = n * n;//ans表示最优解通过的数量
	if (n % 2 == 0) {
		for (int i = 1; i <= n; i ++)
			m[i][n - i + 1] = 1;
		ans -= n;
	}//n是偶数的情况处理
	printf("%d\n", ans);
	int ux = 0, uy = 0;//u表示当前的点
	while (!(ux == n && uy == n)) {
		int vx, vy;//v表示可能的下一个点
		vx = ux - 1;
		vy = uy - 1;
		if (0 <= vx && vx <= n && 0 <= vy && vy <= n && !m[ux][uy]) {
			m[ux][uy] = 1;
			ux = vx, uy = vy;
			printf("%d %d\n", vx, vy);
			continue;
		}//左下
		vx = ux + 1;
		vy = uy - 1;
		if (0 <= vx && vx <= n && 0 <= vy && vy <= n && !m[ux + 1][uy]) {
			m[ux + 1][uy] = 1;
			ux = vx, uy = vy;
			printf("%d %d\n", vx, vy);
			continue;
		}//右下
		vx = ux - 1;
		vy = uy + 1;
		if (0 <= vx && vx <= n && 0 <= vy && vy <= n && !m[ux][uy + 1]) {
			m[ux][uy + 1] = 1;
			ux = vx, uy = vy;
			printf("%d %d\n", vx, vy);
			continue;
		}//左上
		vx = ux + 1;
		vy = uy + 1;
		if (0 <= vx && vx <= n && 0 <= vy && vy <= n && !m[ux + 1][uy + 1]) {
			m[ux + 1][uy + 1] = 1;
			ux = vx, uy = vy;
			printf("%d %d\n", vx, vy);
			continue;
		}//右上
	}
	return 0;
}

我授权可以对此方法发表个人题解，方法思路那一栏挂我就行