(C卷,200分)- 连续出牌数量（Java & JS & Python & C）

题目描述

有这么一款单人卡牌游戏，牌面由颜色和数字组成，颜色为红、黄、蓝、绿中的一种，数字为0-9中的一个。游戏开始时玩家从手牌中选取一张卡牌打出，接下来如果玩家手中有和他上一次打出的手牌颜色或者数字相同的手牌，他可以继续将该手牌打出，直至手牌打光或者没有符合条件可以继续打出的手牌。

现给定一副手牌，请找到最优的出牌策略，使打出的手牌最多。

输入描述

输入为两行

• 第一行是每张手牌的数字，数字由空格分隔，
• 第二行为对应的每张手牌的颜色，用r y b g这4个字母分别代表4种颜色，字母也由空格分隔。

手牌数量不超过10。

输出描述

输出一个数字，即最多能打出的手牌的数量。

用例

题目解析

本题连续出牌的条件是：

如果玩家手中有和他上一次打出的手牌颜色或者数字相同的手牌，他可以继续将该手牌打出

因此，我们可以基于回溯算法，来求解不同的出牌方式，而下张牌是否可出的条件是：

• 和上一张牌的数字相同，或者和上一张牌的颜色相同

JS算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines = [];
rl.on("line", (line) => {
  lines.push(line);

  if (lines.length === 2) {
    const nums = lines[0].split(" ");
    const colors = lines[1].split(" ");

    console.log(getMaxCount(nums, colors));

    lines.length = 0;
  }
});

class Card {
  constructor(num, color) {
    this.num = num;
    this.color = color;
  }
}

function getMaxCount(nums, colors) {
  const n = nums.length;

  const cards = [];
  for (let i = 0; i < n; i++) {
    cards[i] = new Card(nums[i], colors[i]);
  }

  const ans = [0];
  const used = new Array(n).fill(false);

  dfs(cards, used, undefined, 0, ans);
  return ans[0];
}

function dfs(cards, used, last, count, ans) {
  ans[0] = Math.max(ans[0], count);

  for (let i = 0; i < cards.length; i++) {
    if (used[i]) continue;

    const cur = cards[i];
    if (last && last.num != cur.num && last.color != cur.color) continue;

    used[i] = true;
    dfs(cards, used, cur, count + 1, ans);
    used[i] = false;
  }
}

Java算法源码

import java.util.Arrays;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    int[] nums = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    String[] colors = sc.nextLine().split(" ");

    System.out.println(getResult(nums, colors));
  }

  static class Card {
    int num;
    char color;

    public Card(int num, String color) {
      this.num = num;
      this.color = color.charAt(0);
    }
  }

  public static int getResult(int[] nums, String[] colors) {
    int n = nums.length;
    Card[] cards = new Card[n];
    for (int i = 0; i < n; i++) cards[i] = new Card(nums[i], colors[i]);

    int[] ans = {0};
    boolean[] used = new boolean[n];
    dfs(cards, used, null, 0, ans);
    return ans[0];
  }

  public static void dfs(Card[] cards, boolean[] used, Card last, int count, int[] ans) {
    ans[0] = Math.max(ans[0], count);

    for (int i = 0; i < cards.length; i++) {
      if (used[i]) continue;

      Card cur = cards[i];
      if (last != null && last.num != cur.num && last.color != cur.color) continue;

      used[i] = true;
      dfs(cards, used, cur, count + 1, ans);
      used[i] = false;
    }
  }
}

Python算法源码

# 输入获取
nums = input().split()
colors = input().split()


def dfs(cards, used, last, count, ans):
    ans[0] = max(ans[0], count)

    for i in range(len(cards)):
        if used[i]:
            continue

        cur = cards[i]
        if last and last.num != cur.num and last.color != cur.color:
            continue

        used[i] = True
        dfs(cards, used, cur, count + 1, ans)
        used[i] = False


class Card:
    def __init__(self, num, color):
        self.num = num
        self.color = color


# 算法入口
def getResult():
    n = len(nums)

    cards = [Card(nums[i], colors[i]) for i in range(n)]

    ans = [0]
    used = [False] * n

    dfs(cards, used, None, 0, ans)

    return ans[0]


# 算法调用
print(getResult())

C算法源码

#include <stdio.h>

#define MAX(a,b) ((a) > (b) ? (a) : (b))

#define MAX_SIZE 10

typedef struct {
    int num;
    char color;
} Card;

// 记录题解
int ans = 0;

// 记录输入的卡牌信息
Card cards[MAX_SIZE];
int cards_size = 0;

// 回溯求解所有出牌情况
void dfs(int used[], Card* last, int count);

int main() {
    while (scanf("%d", &cards[cards_size].num)) {
        cards_size++;
        if (getchar() != ' ') break;
    }

    for (int i = 0; i < cards_size; i++) {
        cards[i].color = (char) getchar();
        getchar();
    }

    // 记录哪些牌使用过了
    int used[MAX_SIZE] = {0};
    dfs(used, NULL, 0);

    printf("%dn", ans);

    return 0;
}

void dfs(int used[], Card* last, int count) {
    ans = MAX(ans, count);

    for(int i=0; i<cards_size; i++) {
        // 如果当前牌已经使用过，则不能出牌
        if(used[i]) continue;

        // 当前牌
        Card cur = cards[i];

        // 如果 和上一张牌的数字不同，且和上一张牌的颜色也不同，则不能出牌
        if(last != NULL && last->num != cur.num && last->color != cur.color) continue;

        used[i] = 1;
        dfs(used, &cur, count + 1);
        used[i] = 0;
    }
}