自动搬运

查看原文

来自洛谷，原作者为

	QianianXY www.qianianxy.cn

搬运于2025-08-24 21:26:25，当前版本为作者最后更新于2019-07-18 22:45:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题的本质不难，大概也就黄题的水平，dfs即可。（我是不会告诉你我提交了3次才AC）

到达下一只牛（dfs下一步)的条件：

1、与当前的牛的x轴或y轴坐标相等。

2、需要转弯才能到达。

3、此前未经过。

第一个重点在于第二个条件，如何判断是否存在转弯？这里使用一个函数，通过对起始点和目标点的判断，返回线路的方向：

inline int dire(int x, int y, int x1, int y1) {
	// 因为条件1，所以只用判断不相同的轴的大小关系。
	if (x < x1) return 1;
	if (x > x1) return 2;
	if (y < y1) return 3;
	if (y > y1) return 4;
}

第二个重点是判断是否为一条路径。为所有点定义一个bool数组，记录是否已经经过。在dfs函数的开头判断是否所有点都已经经过，如果成立，判断是否能在转弯后回到原点。如果仍然成立，则计数器加1。

最后代码如下：（码风欠佳请见谅）

#include <cstdio>
#include <cstring>
using namespace std;
struct point {int x, y;} p[11];
int n, ans = 0;
bool b[11], c;
inline int dire(int x, int y, int x1, int y1) {
	if (x < x1) return 1;
	if (x > x1) return 2;
	if (y < y1) return 3;
	if (y > y1) return 4;
}
void dfs(int x, int y, int d) {
	c = true;
	for (register int i = 0; i < n; i++)
		if (b[i]) {
			c = false; break;
		} 
	if (c && (x == 0 || y == 0) && dire(x, y, 0, 0) != d)  {
		ans++; return;
	}
	for (register int i = 0; i < n; i++)
		if ((p[i].x == x || p[i].y == y) && b[i] && dire(x, y, p[i].x, p[i].y) != d) {
			b[i] = false;
			dfs(p[i].x, p[i].y, dire(x, y, p[i].x, p[i].y));
			b[i] = true;
		}
}
int main() {
	memset(b, true, sizeof(b));
	scanf("%d", &n);
	for (register int i = 0; i < n; i++) scanf("%d%d", &p[i].x, &p[i].y);
	dfs(0, 0, 0);
	printf("%d\n", ans);
	return 0;****
}

（没错，加黑的那两处正是我两次WA的原因）

看着小蒟蒻写得那么认真，不点个赞再走吗？