剪邮票


如【图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数组转换成修正编号