AT_abc335_d [ABC335D] Loong and Takahashi 题解

题目传送门

题目大意：

高桥在一个地图的中心，有一条龙从地图的左上角开始，每次只能到达与他相邻的四个点，现给出地图的边长，请你给出一种方案，使得地图上的每个点除高桥所在的地方外，都被龙走过且不重复。

解题思路：

首先，我们拿到这个题目，想十秒，便会发现，我们按照螺旋矩阵的方式行走，一定是符合题意的，于是我们就开始模拟：

1. 如果我们没有走到最后一列，则向右走一列，并跳过此次循环。
2. 如果我们没有走到最后一行，则向下走一行，并跳过此次循环。
3. 如果我们没有走到第一列，则向左走一列，并跳过此次循环。
4. 如果我们没有走到第一行，则向上走一行。

然后，我们就会发现，我们会走到重复的点。

于是，我们看了看 $n$ 的数据范围，很小，所以直接定义一个数组标记，在模拟时判断当前点是否走过，然后直接执行下一步即可。

AC CODE:

#include <bits/stdc++.h>
using namespace std;
int c[50][50];
int main() {
	ios::sync_with_stdio(false);
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int n;
	cin >> n;
	c[n / 2 + 1][n / 2 + 1] = 114514;
	int x = 1, y = 1;
	int ans = 1;
	int flag = 1;
	while (ans < n * n) {
		c[x][y] = ans++;
		if (flag == 1)
			y++, flag = (y < n && !c[x][y + 1] ? 1 : 2);
		else if (flag == 2)
			x++, flag = (x < n  && !c[x + 1][y] ? 2 : 3);
		else if (flag == 3)
			y--, flag = (y > 1  && !c[x][y - 1] ? 3 : 4);
		else
			x--, flag = (x > 1  && !c[x - 1][y] ? 4 : 1);
	}
	for (int i = 1; i <= n; i++, cout << endl)
		for (int j = 1; j <= n; j++)
		{
			if (c[i][j] == 114514)
				cout << "T ";
			else
				cout << c[i][j] << ' ';
		}
	return 0;
}

总结

只要做过螺旋矩阵的都很容易想到正解，这题主要还是考察我们运用知识的能力，所以大家一定要将知识都掌握牢，懂得变通，才能走得更远。