Henry-ji 的小站

精品资源，小知识分享

0%

UVA10503 题解

发表于 分类于 Valine：
本文字数： 457 阅读时长 ≈ 1 分钟

一、题意分析

总结题中的骨牌特性：两点、双向，你会想到什么？

请思考 3 秒钟

没错，答案就是无向图

我们以一组输入为例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
10
13
1 0
6 4
0 4
0 4
0 3
5 1
6 0
0 3
1 6
2 4
6 6
6 0
1 6
3 5
4 3

由以上的数据我们可以做出一个无向图（见右图）

图中的红色箭头分别为开始和结束的骨牌（$(1, 0)、(6, 4)$）

所以，题目就转化为能否找到一条从 $0$ 到 $6$ 的长度为 $10$ 的路线

二、思路总结

显然，对于本题来说，深度优先搜索是最好的选择。那么，什么是深度优先搜索？

深度优先搜索 (DFS) 全称是 Depth First Search，是一种用于遍历或搜索树或图的算法。所谓深度优先，就是说每次都尝试向更深的节点走。

—— OI Wiki

要想正确地用递归写出一段 DFS 的代码，我们需要知道以下信息：

  • 每次递归需要做什么？
  • 递归的结束条件是什么？
  • DFS 的回溯条件是什么？
请仔细思考一下，思考完成后点击左边的箭头展开答案

> 每次递归获取一个编号并寻找包含这个编号的骨牌，再以该骨牌的另一个编号进行下一次递归
> 距离达标且当前编号等于结束编号
> 距离达标但当前编号不等于结束编号

三、AC 代码

C++

C++ 的码风略差，将就着看看吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>

using namespace std;

struct card {  // 骨牌类
    int lst, nxt;  // 此处的 lst，nxt 不代表前后关系，仅表示两者互为正反面关系（除了开头和结尾的两个骨牌）
    bool flag = false;  // 记录这张骨牌是否使用过
} start, ed, cur_card, cardList[1000000];  // 记录所有中间骨牌
int n, m;
bool solved;  // 全局记录是否有解


void find_next(int card, int distance) {  // dfs
    if (distance == n and card == ed.lst) {  // 符合条件：距离达标且与末尾骨牌连接
        solved = true;
        return;
    }
    if (distance >= n) return;  // 距离已到但未匹配成功
    for (int c = 0; c < m; c++) {
        cur_card = cardList[c];
        if (cur_card.lst == card and !cur_card.flag) {  // 前后分别遍历
            cardList[c].flag = true;  // 标记该骨牌以使用过
            find_next(cur_card.nxt, distance + 1);  // dfs 搜索，每次深度 +1
            cardList[c].flag = false;  // dfs 回溯，标记改为未使用状态
        } else if (cur_card.nxt == card and !cur_card.flag) {
            cardList[c].flag = true;
            find_next(cur_card.lst, distance + 1);
            cardList[c].flag = false;
        }
    }

}


int main() {
    while (true) {
        cin >> n;
        if (n == 0) return 0;
        cin >> m;
        cin >> start.lst >> start.nxt;
        cin >> ed.lst >> ed.nxt;
        for (int i = 0; i < m; i++) cin >> cardList[i].lst >> cardList[i].nxt;
        solved = false;
        find_next(start.nxt, 0);
        if (solved) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
}

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class CLS_card(object):
    def __init__(self, lst, nxt):  # 骨牌类
        self.lst = lst
        self.nxt = nxt  # 此处的 lst，nxt 不代表前后关系，仅表示两者互为正反面关系（除了开头和结尾的两个骨牌）
        self.flag = False  # 记录这张骨牌是否使用过


def find_next(card, distance):  # dfs
    global solved
    if distance == n and card == end.lst:  # 符合条件：距离达标且与末尾骨牌连接
        solved = True
        return
    if distance >= n:  # 距离已到但未匹配成功
        return
    for c in cardList:
        if c.lst == card and c.flag == False:  # 前后分别遍历
            c.flag = True  # 标记该骨牌以使用过
            find_next(c.nxt, distance + 1)  # dfs 搜索，每次深度 +1
            c.flag = False  # dfs 回溯，标记改为未使用状态
        elif c.nxt == card and c.flag == False:
            c.flag = True
            find_next(c.lst, distance + 1)
            c.flag = False


while True:
    n = eval(input())
    if n == 0:
        break
    m = eval(input())
    inp = input().split()
    start = CLS_card(int(inp[0]), int(inp[1]))
    inp = input().split()
    end = CLS_card(int(inp[0]), int(inp[1]))
    cardList = []  # 记录所有中间骨牌
    for i in range(m):
        inp = input().split()
        cardList.append(CLS_card(int(inp[0]), int(inp[1])))
    solved = False  # 全局记录是否有解
    find_next(start.nxt, 0)
    if solved:
        print('YES')
    else:
        print('NO')