题解 P1556 【幸福的路】

· · 题解

题的本质不难，大概也就黄题的水平，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的原因）

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