演算法 程式問題 20點急

Snowflake Snow Snowflakes

Description

You may have heard that no two snowflakes are alike. Your task is to write a

program to determine whether this is really true. Your program will read information

about a collection of snowflakes, and search for a pair that may be identical. Each

snowflake has six arms. For each snowflake, your program will be provided with a

measurement of the length of each of the six arms. Any snowflake with the same

lengths of corresponding arms should be flagged by your program as possibly

identical.

Input

The first line of input will contain a single integer n, 0 < n ≤ 100000, the number

of snowflakes to follow. This will be followed by n lines, each describing a snowflake.

Each snowflake will be described by a line containing six integers (each integer is at

least 0 and less than 10000000), the lengths of the arms of the snow ake. The lengths

of the arms will be given in order around the snowflake (either clockwise or

counterclockwise), but they may begin with any of the six arms. For example, the

same snowflake could be described as 1 2 3 4 5 6 or 4 3 2 1 6 5.

Output

If all of the snowflakes are distinct, your program should print the message:

No two snowflakes are alike.

If there are possibly identical snowflakes, your program should print the message:

The following snowflakes are identical:

<a list of identical snowflakes>

Sample Input 1

4

1 2 3 4 5 6

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

6 5 2 4 3 1

Sample Output 1

The following snowflakes are identical:

1 2 3 4 5 6

4 3 2 1 6 5

The following snowflakes are identical:

1 3 4 2 5 6

6 5 2 4 3 1

Sample Input 2

2

1 2 3 4 5 6

4 5 2 1 6 3

Sample Output 2

No two snowflakes are alike.

Source

CCC 2007

1. 問題描述

2. 解題構想

3. 資料結構與演算法

4. 程式流程圖

5. 程式執行畫面

6. 程式碼 (含註解)

1 Answer

Rating
  • sponge
    Lv 6
    7 years ago
    Favorite Answer

    請參考:

    // In C++

    #include <cstdio>

    #include <map>

    #include <string>

    #include <vector>

    using namespace std;

    int main(){

    char snowflake[100]; // 讀一行的 buffer

    // 六層索引 (key) 的 map, 來自六個 arm

    // map 的值 (value) 是那個 snowflake 所屬類別 ID

    map<int, map<int, map<int, map<int, map<int, map<int, int> > > > > > T;

    vector<vector<string> > S; // snowflake 類別

    int line; // 檔案幾行

    scanf("%d\n", &line);

    for (int i=0; i<line; i++) {

    int arm[6];

    // 讀 snowflake

    fgets(snowflake, sizeof(snowflake), stdin);

    sscanf(snowflake, "%d%d%d%d%d%d", &arm[0], &arm[1], &arm[2], &arm[3], &arm[4], &arm[5]);

    // 已經有類似的 snowflake

    if (T[arm[0]][arm[1]][arm[2]][arm[3]][arm[4]].count(arm[5]))

    S[T[arm[0]][arm[1]][arm[2]][arm[3]][arm[4]][arm[5]]].push_back(snowflake);

    // 沒類似的 snowflake, 把所有可能加入到 T

    else {

    for (int j=0; j<6; j++) {

    T[arm[j]][arm[(j+1)%6]][arm[(j+2)%6]][arm[(j+3)%6]][arm[(j+4)%6]][arm[(j+5)%6]]=S.size();

    T[arm[(j+5)%6]][arm[(j+4)%6]][arm[(j+3)%6]][arm[(j+2)%6]][arm[(j+1)%6]][arm[j]]=S.size();

    }

    S.resize(S.size()+1);

    S.back().push_back(snowflake);

    }

    }

    // 輸出結果

    if (S.size()<line) {

    for (size_t i=0; i<S.size(); i++) {

    // 跳過沒相同的 snowflake

    if (S[i].size()==1) continue;

    puts("The following snowflakes are identical: ");

    for (size_t j=0; j<S[i].size(); j++)

    printf(S[i][j].c_str());

    }

    }

    else puts("No two snowflakes are alike.");

    return 0;

    }

    當 a b c d e f 被認為是新的 snowflake

    則順時針考慮六種狀況:

    a b c d e f

    b c d e f a

    c d e f a b

    ...

    f a b c d e

    逆時針也考慮六種狀況:

    f e d c b a

    e d c b a f

    d c b a f e

    ...

    a f e d c b

    將這些資訊插入 map 中

    T 的索引有六層,就是利用這個方式填入

    當發現新的 snowflake, 會在 S 註冊新的 snowflake 類別

    舊的 S.size() 當作新類別的 ID, 註冊完 S.size() 就 +1

    ID 會存在 T 經過六個 arm 的索引後查出來的類別值

    相信有更有效率的做法,版主有興趣可自行爬文

    希望以上回答對您有幫助!

Still have questions? Get your answers by asking now.