首页 > 试题广场 >

多多的骰子组合

[编程题]多多的骰子组合
  • 热度指数:1687 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
多多君拼团购买了N个骰子,为了方便后面进行活动,多多君需要将这些骰子进行分类。



两个骰子为同类的定义是:
将其中一个骰子通过若干次上下、左右或前后翻转后,其与另一个骰子对应的6面数字均相等。

现在多多君想知道不同种类的骰子的数量分别有多少。

输入描述:
第一行1个整数N,表示骰子的数量。
(1 <= N <= 1,000)
接下来N行,每行6个数字(1~6,且各不相同)
其中第i行表示第i个骰子当前上、下、左、右、前、后这6面的数字。


输出描述:
共2行:
第一行1个整数M,表示不同种类的骰子的个数
第二行M个整数,由大到小排序,表示每个种类的骰子的数量
示例1

输入

2
1 2 3 4 5 6
1 2 6 5 3 4

输出

1
2

说明

第二个骰子相当于是第一个骰子从左向右旋转了一面得到,属于同类。
示例2

输入

3
1 2 3 4 5 6
1 2 6 5 3 4
1 2 3 4 6 5

输出

2
2 1

说明

第三个骰子无法通过任何旋转变换成第一个或第二个骰子。
示例3

输入

10
2 5 1 3 4 6
5 4 3 2 1 6
1 4 6 2 3 5
1 5 6 3 4 2
6 4 2 1 5 3
3 6 4 5 2 1
1 6 3 4 2 5
5 1 4 2 6 3
6 2 3 1 5 4
5 3 6 1 4 2

输出

9
2 1 1 1 1 1 1 1 1

说明

只有第4个骰子(1 5 6 3 4 2)与第8个骰子(5 1 4 2 6 3)属于同一类。

一种可能的变换方式:
1) 首先从右向左翻转1次
 (1 5 6 3 4 2) -> (1 5 4 2 3 6)
2) 然后从上向下翻转2次
 (1 5 4 2 3 6) -> (6 3 4 2 1 5) -> (5 1 4 2 6 3)

备注:
对于50%的数据,有: 1 <= N <= 50
对于100%的数据,有:1 <= N <= 1,000
Java 硬模拟,骰子就两种旋转方式,水平和垂直。每个骰子都固定top为1,固定左面小于右面,前面小于后面,则每类骰子的情况唯一。
import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n = Integer.parseInt(in.nextLine());
        HashMap<String, Integer> myhashMap = new HashMap<>();
        for (int i = 0; i < n; i++) {
            String line = in.nextLine();
            Touzi temp = new Touzi(line);
          
            myhashMap.put(temp.toString(),myhashMap.getOrDefault(temp.toString(),0)+1);
        }
        System.out.println(myhashMap.keySet().size());
        ArrayList<Integer> result=new ArrayList<>();
        for(String key:myhashMap.keySet()){
            result.add(myhashMap.get(key));
        }
        result.sort((x,y)->y-x);
        for(Integer i:result){
            System.out.print(i+" ");
        }
    }
}
class Touzi {
    public int top;
    public int bottom;
    public int left;
    public int right;
    public int front;
    public int behind;
    Touzi(String line) {
        String [] temps = line.split(" ");
        top = Integer.parseInt(temps[0]);
        bottom = Integer.parseInt(temps[1]);
        left = Integer.parseInt(temps[2]);
        right = Integer.parseInt(temps[3]);
        front = Integer.parseInt(temps[4]);
        behind = Integer.parseInt(temps[5]);
        while (top != 1) {
            if (bottom == 1 || behind == 1 || front == 1) {
                verticalswap();
            } else {
                horizontalswap();
            }
        }
        while (left > right||front>behind) {
            horizontalswap();
        }
    }
    public String toString() {
        return top+ "" + bottom +""+ left+"" + right+"" + front+"" + behind ;
    }
    public void horizontalswap() {
        int templeft = this.left;
        int tempright = this.right;
        int tempfront = this.front;
        int tempbehind = this.behind;
        this.left = tempfront;
        this.behind = templeft;
        this.right = tempbehind;
        this.front = tempright;
    }
    public void verticalswap() {
        int tempfront = this.front;
        int tempbehind = this.behind;
        int temptop = this.top;
        int tempbottom = this.bottom;
        this.front = temptop;
        this.bottom = tempfront;
        this.behind = tempbottom;
        this.top = tempbehind;
    }
}


发表于 2024-08-11 13:32:01 回复(0)