Usaco Training [1.3] wormhole

103 阅读 0 评论 68 点赞

我是靠谱客的博主辛勤中心，最近开发中收集的这篇文章主要介绍Usaco Training [1.3] wormhole，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

传送门

解题要素：代码能力

解题步骤：理解题意 - 》搜索枚举所有可能的配对情况 - 》判断冲突并求解 - 》调试

一. 理解题意

　　这里讲几个不容易理解的点：

　　　　1. +x方向即向右走

　　　　2. 一旦来到虫洞，就必须掉入

二. 搜索枚举所有可能的配对情况

　　考虑引入match数组，对于当前的节点来说，枚举后面的点是否已配对过即可

 1 int match[N];
 2 inline void dfs(int x) { //当前节点
 3
if (x == n + 1) {
 4
rep(i, 1, n) if (check(i, i, 1, 0)) {
 5
ans++;
 6
break;
 7 
}
 8
return;
 9 
}
10
if (match[x]) dfs(x + 1); //已有匹配，无需枚举
11
else {
12
rep(i, x + 1, n) if (!match[i]) { //枚举
13
match[i] = x, match[x] = i;
14
dfs(x + 1);
15
match[i] = match[x] = 0; //回溯
16 
}
17 
}
18 }

三. 判断冲突并求解

　　代码的核心部分，分析当前的一个状态有哪些量是相关的，加上对于题目的理解

 1 int ans;
 2 inline bool check(int begin, int now, int length, int state) { //state - 0 : walk 1 : worm
 3
if (length > 1 && now == begin && state == 0) return 1; //回到原点了，而且是用走的方式
 4
if (state == 0) { //走到虫洞口了就跳进去
 5
check(begin, match[now], length + 1, 1);
 6 
}
 7
else { //从虫洞d出来，就往前走，如果前面有虫洞，就走过去，没有就返回0
 8
if (a[now].y == a[now + 1].y) check(begin, now + 1, length + 1, 0); else return 0;
 9 
}
10 }

四. 调试

　　1.读入的坐标轴是与正常的行列相反的，在排序和判同行时须格外注意

　　2.因为奶牛所在初始虫洞处时便掉进去，所以最终只有可能走到虫洞处

最终的代码：

 1 /*
 2 PROG: wormhole
 3 LANG: C++
 4 */
 5 #include <bits/stdc++.h>
 6 using namespace std;
 7 #define rep(i, a, b) for(int i = a; i <= b; ++i)
 8
 9 const int N = 20;
10
11 int n;
12 struct node {
13
int x, y;
14 }a[N];
15
16 bool cmp(const node &a, const node &b) {
17
return a.y == b.y ? a.x < b.x : a.y < b.y;
18 }
19
20 int match[N], ans;
21
22 inline bool check(int begin, int now, int length, int state) { //state - 0 : walk 1 : worm
23
if (length > 1 && now == begin && state == 0) return 1;
24
if (state == 0) {
25
check(begin, match[now], length + 1, 1);
26 
}
27
else {
28
if (a[now].y == a[now + 1].y) check(begin, now + 1, length + 1, 0); else return 0;
29 
}
30 }
31
32 inline void dfs(int x) {
33
if (x == n + 1) {
34
rep(i, 1, n) if (check(i, i, 1, 0)) {
35
ans++;
36
break;
37 
}
38
return;
39 
}
40
if (match[x]) dfs(x + 1);
41
else {
42
rep(i, x + 1, n) if (!match[i]) {
43
match[i] = x, match[x] = i;
44
dfs(x + 1);
45
match[i] = match[x] = 0;
46 
}
47 
}
48 }
49
50 int main() {
51
freopen("wormhole.in", "r", stdin);
52
freopen("wormhole.out", "w", stdout);
53
scanf("%d", &n);
54
rep(i, 1, n) {
55
scanf("%d%d", &a[i].x, &a[i].y);
56 
}
57
sort(a + 1, a + n + 1, cmp);
58
dfs(1);
59
printf("%dn", ans);
60
return 0;
61 }