连接奶牛

2022/5/23 23:22:47

本文主要是介绍连接奶牛,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

连接奶牛

每天农夫约翰都会去巡视农场,检查他的 $N$ 头奶牛的健康状况。

每头奶牛的位置由二维平面中的一个点描述,而约翰从原点 $\left( {0,0} \right)$ 出发。

所有奶牛的位置互不相同,且都不在原点。

为了使自己的路线更有趣,农夫约翰决定只沿平行于坐标轴的方向行走,即只能向北,向南,向东或向西行走。

此外,他只有在到达奶牛的位置时才能改变行进方向(如果需要,他也可以选择通过奶牛的位置而不改变方向)。

在他改变方向时,可以选择转向 $90$ 或 $180$ 度。

约翰的行进路线必须满足在他访问完所有奶牛后能够回到原点。

如果他在每头奶牛的位置处恰好转向一次,请计算出约翰访问他的 $N$ 头奶牛可以采取的不同路线的数量。

允许他在不改变方向的情况下通过任意奶牛的位置任意次数

同一几何路线正向走和反向走算作两条不同的路线。

输入格式

第一行包含整数 $N$。

接下来 $N$ 行,每行包含两个整数 $\left( {x,y} \right)$ 表示一个奶牛的位置坐标。

输出格式

输出不同路线的数量。

如果不存在有效路线,则输出 $0$。

数据范围

$1 \leq N \leq 10$,
$−1000 \leq x,y \leq 1000$

输入样例:

1 4
2 0 1
3 2 1
4 2 0
5 2 -5

输出样例:

2

样例解释

共有两条不同路线 $1−2−4−3$ 和 $3−4−2−1$。

 

解题思路

  如果一个点要到达另外一个点,离开这个点的发方向可以与到达这个点方向相差$90$度或$180$度,但不可以相差$0$度。即离开这个点的方向必须与到达这个点的方向不一样。题目要求每个点恰好转向一次,意味着每个点最多会遍历一次。并且题目要求每个点都必须被遍历一次。

  可以发现任意一种走法可以唯一对应一个全排列,因为每一个走法相当于按顺序走每一个点。反过来任意一个全排列最多会对应一种走法,在全排列中我们任意找相邻的两个数$a$和$b$,可以发现$a$到$b$的方向是唯一的,只有一种走法,因此一个全排列最多会对应一种走法。因此任意两种走法不可能对应同一个全排列,即不同走法会对应不同的全排列。

  所以如果要求所有走法的数量,可以求所有合法的全排列(如果直接求走法会比较难写)。这个全排列要满足:

  1. 能够从$\left( {0,0} \right)$走到全排列的第一个点。
  2. 能够从全排列的最后一个点走到$\left( {0,0} \right)$这个点。
  3. 全排列中任意两个相邻的点在同一条直线上。
  4. 全排列中相邻的$3$个点的行走方向的要不同。(例如在全排列中有$abc$,$a$到$b$的方向是向右,$b$到$c$的方向也是向右,这就不合法了)

  这种写法就是枚举所有可能的答案,再找到合法的方案,而不是正面直接去求所有合法的答案。会这么想是因为所有的路径的方案数就是$n$的全排列,所以我们可以枚举$n$的所有全排列,不可能还会有其他的方案了,然后再去判断这个全排列是否可以对应一条合法的路径,这种写法会相对更简单。

  AC代码如下,时间复杂度为$O \left( n \times n! \right)$:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int N = 15;
 5 
 6 int x[N], y[N];
 7 int p[N];   // 全排列数组
 8 
 9 // 从a到b的方向,规定向上为0,向右为1,向下为2,向左为3
10 int get(int a, int b) {
11     if (x[a] != x[b] && y[a] != y[b]) return -1;    // a和b不再同一条直线上
12     
13     if (x[a] == x[b]) {
14         if (y[b] > y[a]) return 0;  // a向上走到b
15         return 2;   // a向下走到b
16     }
17     
18     if (x[b] > x[a]) return 1;  // a向右走到b
19     return 3;   // a向左走到b
20 }
21 
22 int main() {
23     int n;
24     scanf("%d", &n);
25     for (int i = 1; i <= n; i++) {
26         scanf("%d %d", x + i, y + i);
27     }
28     for (int i = 1; i <= n; i++) {
29         p[i] = i;   // 初始时全排列为123...n
30     }
31     
32     int ret = 0;
33     do {    // 从最小全排列枚举到最大全排列
34         int last = get(0, p[1]);    // 从0到全排列第一个点的方向
35         if (last == -1) continue;
36         
37         for (int i = 1; i <= n; i++) {
38             int d = get(p[i], p[i + 1]);    // 到下一个点的方向
39             if (d == -1 || d == last) {     // 如果不可以到达下一个点,或者到达下一个点与到达当前点的方向相同
40                 last = -1;  // 当前的全排列不合法
41                 break;
42             }
43             last = d;   // 更新方向
44         }
45         
46         if (last != -1) ret++;
47     } while (next_permutation(p + 1, p + 1 + n));   // 返回下一个全排列,如果已经是最大的全排列,返回false
48     
49     printf("%d", ret);
50     
51     return 0;
52 }

   这题还可以用动态规划来做。当$N = 20$时上面那种做法就会超时了(不过状压dp也很悬)。为了确定状态的表示,我们先看看最终所有合法的方案都满足什么特征,找到这些合法方案的共同特征,然后用这些特征来表示状态,进而表示这些方案,并尝试找到状态转移方程。

  可以发现,最终合法的方案都满足每个点$\left( 1 \sim n \right)$被遍历过一次,我们再把这些方案根据最后一个点的编号,划分为$n$个集合,以及考虑到点的移动需要用到上一次移动的方向,因此这$n$个集合中,每个集合又可以分成$4$个小集合,分别表示到这个点的$4$个不同的方向。这样我们就把所有的方案都划分完成,需要用到$3$个状态来表示这些方案,一个是已经遍历过点(用二进制表示),最后一个点的编号,以及到最后一个点的方向。

  AC代码如下,时间复杂度为$O \left( 2^{n} \times n^{2} \right)$:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int N = 11, M = 1 << N;
 5 
 6 int x[N], y[N];
 7 int f[M][N][4];
 8 
 9 int get(int a, int b) {
10     if (x[a] != x[b] && y[a] != y[b]) return -1;
11     
12     if (x[a] == x[b]) {
13         if (y[b] > y[a]) return 0;
14         return 2;
15     }
16     
17     if (x[b] > x[a]) return 1;
18     return 3;
19 }
20 
21 int main() {
22     int n;
23     scanf("%d", &n);
24     for (int i = 1; i <= n; i++) {
25         scanf("%d %d", x + i, y + i);
26     }
27     
28     // 初始化
29     for (int i = 0; i < n; i++) {
30         int d = get(0, i + 1);  // 由于存储的坐标从1开始,因此求两点的转移方向时点的下标要+1,映射到存储下标
31         if (d != -1) f[1 << i][i][d] = 1;   // 一开始如果能从(0, 0)到i,则最后一个遍历的点为i且到i的方向为d
32     }
33     
34     for (int i = 0; i < 1 << n; i++) {  // 枚举状态,即遍历过的点
35         for (int j = 0; j < n; j++) {   // 枚举遍历到的最后一个点的编号
36             if (i >> j & 1) {           // j这个点要被遍历过
37                 for (int k = 0; k < n; k++) {   // 枚举遍历到的上一个点
38                     if (k != j && i >> k & 1) { // 上一个点不能是j,且上一个点k要被遍历过
39                         int d = get(k + 1, j + 1);  // k到j的方向
40                         if (d != -1) {  // k可以转移到j
41                             for (int u = 0; u < 4; u++) {   // 枚举4个方向
42                                 if (u == d) continue;       // 转移到k的方向不能够与从k转移到j的方向相同
43                                 f[i][j][d] += f[i - (1 << j)][k][u];
44                             }
45                         }
46                     }
47                 }
48             }
49         }
50     }
51     
52     int ret = 0;
53     for (int i = 0; i < n; i++) {
54         int d = get(i + 1, 0);  // 遍历到的最后一个点到(0, 0)的方向
55         if (d != -1) {  // 可以从最后一个点转移到(0, 0)
56             for (int j = 0; j < 4; j++) {   // 枚举4个方向
57                 if (j == d) continue;   // 相邻3个点的转移方向不能相同
58                 ret += f[(1 << n) - 1][i][j];
59             }
60         }
61     }
62     printf("%d", ret);
63     
64     return 0;
65 }

 

参考资料

  AcWing 2023. 连接奶牛(春季每日一题2022):https://www.acwing.com/video/3877/



这篇关于连接奶牛的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程