机考 出牌顺序 dfs

题目：

给定一堆牌，每张牌都有数字和颜色，选手从中选出一张后，只能再挑选颜色或者数字和上一张相同的牌，否则不能抽选

选手应该怎么选才能使得抽选的次数最大，并且输入这个最大次数

输入

第一行 牌的数值n (1<=n<=10)

第二行 牌的颜色（r,l,g,t四种颜色表示)

输入

抽取的最大次数

示例：

输入

4 1 3 5 4

r g t r n

输出

3

---

这个题当时尝试了50分钟没搞出来，因为之前没做过广度优先法的题，没这个思维。后来看了下网友的思路

参考LeetCode547，本质就是BFS进行图的遍历，找到最大连通的子图的节点数
随手写了一下代码，没有进一步进行优化，但是应该是OK的。

1.  
   def findMaxCards(cards):
2.  
   '''
3.  
   广度优先搜索-队列
4.  
   图的遍历，一个节点出对，相连通的节点入对，当队列为空，则表示已经遍历完了一个连通的子图
5.  
   输入：卡片的列表，内容为数字 颜色，如['4r','5r','4n','3t','1g']
6.  
   输出：最大连通子图的卡牌数量
7.  
   '''
8.  
   # 先将输入列表转化成邻接矩阵，若两个节点数字相同或颜色相同，则连通
9.  
   n = len(cards)
10.  
    matrix = [[0 for _ in range(n)] for _ in range(n)]
11.  
    for i in range(n):
12.  
    for j in range(n):
13.  
    if cards[i][0]==cards[j][0] or cards[i][1]==cards[j][1]:
14.  
    matrix[i][j]=1
15.  
    # BFS进行广度搜索，队列实现
16.  
    visited = [0 for _ in range(n)] # 记录访问过的卡片
17.  
    max_res = 0 # 记录最大的连通子图的节点个数
18.  
     
19.  
    temp = 0 # 记录每个连通子图的节点个数
20.  
    for card_idx in range(n):
21.  
    if visited[card_idx]==0:
22.  
    queue = [card_idx]
23.  
    visited[card_idx]=1
24.  
    else:
25.  
    continue
26.  
     
27.  
    while queue:
28.  
    i = queue.pop(0)
29.  
    temp =1
30.  
    for j in range(n):
31.  
    if matrix[i][j]==1 and visited[j]==0 and i!=j:
32.  
    queue.append(j)
33.  
    visited[j]=1
34.  
    max_res = max(max_res,temp)
35.  
    temp = 0
36.  
    return max_res
37.  
     
38.  
    cards = ['4r','5r','4n','3t','1g']
39.  
    print(findMaxCards(cards))

我没看懂，但是我感觉算的并不对

---

我按照这个思路，给了一个例子：

1 2 3 3 5 5

a b b c b a

我需要先把这些牌之间的关系找出来，就是按数字比相等或者按照花色比相同

然后再记录一个map，每次出一张牌，都要将这个牌的map位置1，这样下次就不再找这个牌了

思路就是，假设从每一个牌开始出，计算后面在这个牌为前的所有可能性，然后可以接的牌，再作为前一个牌，去找接下来的其他牌的可能性.......依次查下去，这肯定需要递归的思想。

麻烦的在于，牌出了一次就不能再出了，但是我先按照一个排序查找后，置map，又不能影响后面可能性的map，这就需要每次从一个情况往下找时，用自身独立的map，不影响其他情况。

每次找到一张牌的可能性后，都要计数 1再加上下一次查找的值，返回。

比如说，我先出第一张牌，置map[0]=1；再找下一张牌的可能性, 根据record[0][i] (i!=0)发现只有i=5的可能性； count

然后5再找下一张，置map[5]=1；根据record[0][i] (i!=0)发现只有i=4的可能性； count

然后4再找下一张，置map[4]=1；根据record[0][i] (i!=0)发现有i=1；i=2的可能性；(i=4不能等于自己，和i=5已经用过了，所以排除) count

然后1再找下一张，同时2再找下一张。。。（这就需要同时查两种情况了，算出来的可能性，取最大值返回）

.........

这样到最后，map也满了，或者找不到record == 1的情况了，就返回0，就结束了这个路径的递归查找了。

1.  
   #include <stdio.h>
2.  
   #include <string.h>
3.  
    
4.  
   #define get_max(m,n) (m>n ? m : n)
5.  
    
6.  
   char record[10][10] = {0}; // 记录牌和牌之间的关系
7.  
   int card_num = 0;
8.  
   // pOutNum是这次找到的lastNum接这个牌的最优解
9.  
   int findMatch(char *pMap, int lastNum, int targetNum){
10.  
    char map_temp[10] = {0};
11.  
    int num[10] = {0};
12.  
    int max_num = 0;
13.  
     
14.  
    memcpy(map_temp, pMap, 10);
15.  
    for(int i=0; i<card_num; i ){
16.  
    if(map_temp[i] == 0 && record[lastNum][i] && lastNum != i){
17.  
    map_temp[i] = 1;
18.  
    num[i] = 1 findMatch(map_temp, i, targetNum-1);
19.  
    max_num = get_max(max_num, num[i]);
20.  
    if(targetNum == max_num){
21.  
    printf("%d ", i);
22.  
    break;
23.  
    }
24.  
    }
25.  
    }
26.  
    return max_num;
27.  
    }
28.  
    int main(){
29.  
    // char card[10][2] = {{'1', 'a'}, {'2', 'b'}, {'3', 'a'}, {'3', 'c'}, {'5', 'b'}, {'5', 'a'}};
30.  
    char card[10][2] = {0};
31.  
    char map[10] = {0}; // 记录路径是否用过某个牌
32.  
    int max_num = 0;
33.  
    int num[10] = {0}; // 从i开始的牌的最大值
34.  
     
35.  
    memset(record, 0, sizeof(record));
36.  
    while(scanf("%[0-9]", &card[card_num][0]) != 0){
37.  
    card_num ;
38.  
    if(getchar() == '\n'){
39.  
    break;
40.  
    }
41.  
    }
42.  
    printf("card_num:%d\n", card_num);
43.  
    for(int i=0; i<card_num; i ){
44.  
    scanf("%c ", &card[i][1]);
45.  
    }
46.  
    for(int i=0; i<card_num; i ){
47.  
    printf("card[%d]: %c %c ", i, card[i][0], card[i][1]);
48.  
    }
49.  
    printf("\n");
50.  
     
51.  
    for(int i=0; i<card_num; i ){
52.  
    for(int k=0; k<card_num; k ){
53.  
    if(card[i][0] == card[k][0] || card[i][1] == card[k][1]){
54.  
    record[i][k] = 1;
55.  
    }
56.  
    printf("%d ", record[i][k]);
57.  
    }
58.  
    printf("\n");
59.  
    }
60.  
    for(int i=0; i<card_num; i ){
61.  
    char map_temp[10] = {0};
62.  
    memcpy(map_temp, map, 10);
63.  
    map_temp[i] = 1;
64.  
    printf("\nnum:%d ", i);
65.  
    num[i] = findMatch(map_temp, i, card_num);
66.  
    max_num = get_max(max_num, num[i]);
67.  
    }
68.  
     
69.  
    for(int i=0; i<card_num; i ){
70.  
    if(max_num == num[i]){
71.  
    char map_temp[10] = {0};
72.  
    memcpy(map_temp, map, 10);
73.  
    map_temp[i] = 1;
74.  
    printf("\nnum---:%d ", i);
75.  
    findMatch(map_temp, i, num[i]);
76.  
    }
77.  
    }
78.  
    printf("\nmax:%d\n", max_num 1); // 上面查到的是以某一张牌开始的后面找到的牌数，还应加上自身
79.  
    }

---

上面代码的targetNum其实就是为了找出路径，不然就只要找到返回值的最大值就可以了。

找出经历过的路径也比较麻烦，因为递归的时候并不知道哪个才是最大的可能性，得都找到最大值后，再找到第一张开始的，再来一遍

输入：

1 2 3 3 5 5

a b b c b a

输出：

card_num:6

card[0]: 1 a card[1]: 2 b card[2]: 3 b card[3]: 3 c card[4]: 5 b card[5]: 5 a

1 0 0 0 0 1

0 1 1 0 1 0

0 1 1 1 1 0

0 0 1 1 0 0

0 1 1 0 1 1

1 0 0 0 1 1

num:0

num:1

num:2

num:3

num:4

num:5

num---:0 3 2 1 4 5

num---:3 0 5 4 1 2

max:6

可以看到从牌0和牌3开始，路径都最长

0 5 4 1 2 3

3 2 1 4 5 0

---

我一直对算法类的东西感觉很困难，递归啊之类的，还是得多练

这篇好文章是转载于：学新通技术网