回溯算法算法

最长连续手牌

2025-10-23  本文已影响0人  何以解君愁

 有这么一款单人卡牌游戏,牌面由颜色和数字组成,颜色为红、黄、蓝、绿中的一种,数字为0-9 中的一个。
 游戏开始时玩家从手牌中选取一张卡牌打出,接下来如果玩家手中有和他上一次打出的手牌颜色或者数字相同的手牌,他可以继续将该手牌打出,直至手牌打光或者没有符合条件可以继续打出的手牌。
 现给定一副手牌,请找到最优的出牌策略,使打出的手牌最多。
 输入描述:输入为两行,第一行是每张手牌的数字,数字由空格分隔,第二张为对应的每张手牌的颜色,用r y b g这4个字母分别代表4种颜色,字母也由空格分隔。手牌数量不超过10。
 输出描述:输出一个数字,即最多能打出的手牌的数量。

import java.util.*;

public class Main{
    static int res = 0;
    static boolean[] used;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String[] numberString = sc.nextLine().trim().split("[ ]");
        String[] colorString = sc.nextLine().trim().split("[ ]");
        int[] number = new int[numberString.length];
        char[] color = new char[numberString.length];
        for(int i = 0;i < numberString.length;i++){
            number[i] = Integer.parseInt(numberString[i]);
            color[i] = colorString[i].charAt(0);
        }
        used = new boolean[numberString.length];
        for(int i = 0;i < numberString.length;i++){
            backTracking(number,color,0,number[i],color[i]);
        }
        System.out.print(res);
    }
    
    public static void backTracking(int[] number,char[] color,int length,int num,Character col){
        res = Math.max(length,res);
        for(int i = 0;i < number.length;i++){
            if(used[i]){
                continue;
            }
            if(col == color[i]||number[i] == num){
                used[i] = true;
                backTracking(number,color,length + 1,number[i],color[i]);
                used[i] = false;
            }
        }
    }
}
上一篇 下一篇

猜你喜欢

热点阅读