剪郵票


如【圖1.jpg】, 有12張連在一起的12生肖的郵票。
現在你要從中剪下5張來，要求必須是連著的。
（僅僅連接一個角不算相連）
比如，【圖2.jpg】，【圖3.jpg】中，粉紅色所示部分就是合格的剪取。


請你計算，一共有多少種不同的剪取方法。


請填寫表示方案數目的整數。
注意：你提交的應該是一個整數，不要填寫任何多餘的內容或說明性文字。

題目請參見：http://blog.csdn.net/eventqueue/article/details/50954641

本文是參考下面帖子中10樓的解法：
http://tieba.baidu.com/p/4425964968

【C語言代碼】
#include <stdio.h>

#define A arr[0]
#define B arr[1]
#define C arr[2]
#define D arr[3]
#define E arr[4]

int arr[5]; // 原數組
int map[] = {-9999, 1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14}; // 原數與修正數的對應關係, 0沒有修正數對應
int dir[4] = {-1, -5, 1, 5}; // 修正數 + 方向 = 新修正數

// 判斷一個修正數是否在修正數組中
int in(int n)
{
    int i;
    for (i = 0; i < 5; i++)
    {
        if (map[arr[i]] == n)
            return 1;
    }
    return 0;
}

// 合法性判定: 至少有4個相鄰面的交線, 且每個塊至少有一個相鄰面的交線
int check(void)
{
    int m, m_new;
    int i, j, k;
    int found;

    int faces[4][2]; // 相鄰的面
    int faces_num = 0; // 相鄰的面數

    for (i = 0; i < 5; i++) // 掃描每個塊
    {
        m = map[arr[i]]; // 當前塊的修正數
        found = 0; // 當前塊與多少個方格相鄰
        for (j = 0; j < 4; j++) // 掃描當前塊的四個方向
        {
            m_new = m + dir[j]; // 該方向的修正數
            if (in(m_new)) // 如果修正數在arr數組中, 表示兩方格相鄰
            {
                found++;

                if (faces_num < 4) // faces數組最多只能存4個相鄰面交線數據
                {
                    // 判斷該面交線是否已經存到了faces數組中
                    for (k = 0; k < faces_num; k++)
                    {
                        if ((faces[k][0] == m && faces[k][1] == m_new) || (faces[k][1] == m && faces[k][0] == m_new))
                            break;
                    }
                    // 如果沒有就添加進去, 然後把faces_num的值+1
                    if (k == faces_num) // 循環不是因為break結束
                    {
                        // 大小順序不定
                        faces[faces_num][0] = m;
                        faces[faces_num][1] = m_new;
                        faces_num++;
                    }
                }
            }
        }
        if (found == 0)
            return 0; // 每個塊至少有一個相鄰的面
    }
    return (faces_num >= 4);
}

int main(void)
{
    int cnt = 0;

    // 生成C5_12組合的簡易方法
    for (A = 1; A <= 12; A++)
    {
        for (B = A + 1; B <= 12; B++)
        {
            for (C = B + 1; C <= 12; C++)
            {
                for (D = C + 1; D <= 12; D++)
                {
                    for (E = D + 1; E <= 12; E++)
                    {
                        if (check())
                        {
                            cnt++;
                            printf("[%d] %d %d %d %d %d\n", cnt, A, B, C, D, E);
                        }
                    }
                }
            }
        }
    }

    printf("總數: %d\n", cnt);

    return 0;
}

【運行結果】
[1] 1 2 3 4 5
[2] 1 2 3 4 6
[3] 1 2 3 4 7
[4] 1 2 3 4 8
[5] 1 2 3 5 6
[6] 1 2 3 5 7
[7] 1 2 3 5 9
[8] 1 2 3 6 7
[9] 1 2 3 6 10
[10] 1 2 3 7 8
[11] 1 2 3 7 11
[12] 1 2 5 6 7
[13] 1 2 5 6 9
[14] 1 2 5 6 10
[15] 1 2 5 9 10
[16] 1 2 6 7 8
[17] 1 2 6 7 10
[18] 1 2 6 7 11
[19] 1 2 6 9 10
[20] 1 2 6 10 11
[21] 1 3 5 6 7
[22] 1 5 6 7 8
[23] 1 5 6 7 9
[24] 1 5 6 7 10
[25] 1 5 6 7 11
[26] 1 5 6 9 10
[27] 1 5 6 10 11
[28] 1 5 9 10 11
[29] 2 3 4 5 6
[30] 2 3 4 6 7
[31] 2 3 4 6 8
[32] 2 3 4 6 10
[33] 2 3 4 7 8
[34] 2 3 4 7 11
[35] 2 3 4 8 12
[36] 2 3 5 6 7
[37] 2 3 5 6 9
[38] 2 3 5 6 10
[39] 2 3 6 7 8
[40] 2 3 6 7 10
[41] 2 3 6 7 11
[42] 2 3 6 9 10
[43] 2 3 6 10 11
[44] 2 3 7 8 11
[45] 2 3 7 8 12
[46] 2 3 7 10 11
[47] 2 3 7 11 12
[48] 2 4 6 7 8
[49] 2 5 6 7 8
[50] 2 5 6 7 9
[51] 2 5 6 7 10
[52] 2 5 6 7 11
[53] 2 5 6 9 10
[54] 2 5 6 10 11
[55] 2 6 7 8 10
[56] 2 6 7 8 11
[57] 2 6 7 8 12
[58] 2 6 7 9 10
[59] 2 6 7 10 11
[60] 2 6 7 11 12
[61] 2 6 9 10 11
[62] 2 6 10 11 12
[63] 3 4 5 6 7
[64] 3 4 6 7 8
[65] 3 4 6 7 10
[66] 3 4 6 7 11
[67] 3 4 7 8 11
[68] 3 4 7 8 12
[69] 3 4 7 10 11
[70] 3 4 7 11 12
[71] 3 4 8 11 12
[72] 3 5 6 7 8
[73] 3 5 6 7 9
[74] 3 5 6 7 10
[75] 3 5 6 7 11
[76] 3 6 7 8 10
[77] 3 6 7 8 11
[78] 3 6 7 8 12
[79] 3 6 7 9 10
[80] 3 6 7 10 11
[81] 3 6 7 11 12
[82] 3 7 8 10 11
[83] 3 7 8 11 12
[84] 3 7 9 10 11
[85] 3 7 10 11 12
[86] 4 5 6 7 8
[87] 4 6 7 8 10
[88] 4 6 7 8 11
[89] 4 6 7 8 12
[90] 4 7 8 10 11
[91] 4 7 8 11 12
[92] 4 8 10 11 12
[93] 5 6 7 8 9
[94] 5 6 7 8 10
[95] 5 6 7 8 11
[96] 5 6 7 8 12
[97] 5 6 7 9 10
[98] 5 6 7 9 11
[99] 5 6 7 10 11
[100] 5 6 7 11 12
[101] 5 6 9 10 11
[102] 5 6 10 11 12
[103] 5 7 9 10 11
[104] 5 9 10 11 12
[105] 6 7 8 9 10
[106] 6 7 8 10 11
[107] 6 7 8 10 12
[108] 6 7 8 11 12
[109] 6 7 9 10 11
[110] 6 7 10 11 12
[111] 6 8 10 11 12
[112] 6 9 10 11 12
[113] 7 8 9 10 11
[114] 7 8 10 11 12
[115] 7 9 10 11 12
[116] 8 9 10 11 12
總數: 116

【合法性判定方法】
至少有N - 1個面交線， 且每個方格都至少有一個面交線
N為剪下來的方格總數

【什麼是修正數】
參考資料：http://blog.csdn.net/u014552756/article/details/50946197
原題中12個格子是這樣編號的：
1  2   3  4
5  6   7   8
9 10 11 12
向上為-4，向下為+4，向左為-1，向右為+1
但是位於邊界的數會出現問題，所以重新編號：
1     2    3  4
6     7    8  9
11 12 13 14
向上變為-5，向下為+5
這樣6向左為5，而5不可能在剪下的郵票（arr）中存在，方便判斷。

在用5個for循環生成組合時，使用原編號
在判斷時，通過map數組轉換成修正編號