深搜——蓝桥杯之剪邮票

原文链接：http://www.cnblogs.com/Simon-X/p/6516380.html

题目描述：

 

如【图1.jpg】, 有12张连在一起的12生肖的邮票。

现在你要从中剪下5张来，要求必须是连着的。

（仅仅连接一个角不算相连） 比如，【图2.jpg】，【图3.jpg】中，粉红色所示部分就是合格的剪取。

请你计算，一共有多少种不同的剪取方法。

和一般的深搜思路不太一样：一般的深搜是定义四个方向，然后依次判断，形成可走的路径，但对于此题，每个路径都可走，因此我们选择顺序判断，即一个点接着一个点进行深搜，每遍历5个点进行判断是否可以形成通路，从(0,0) 开始，(0,1)，(0,2)，(0,3)，(1,0)，然后前四个点不动，继续dfs，直到出界，回溯，前三个点不动，(0,3)到(0,4)，这样做的好处是不用判重，因为不存在重复的情况。

大神写的太简洁了！！！膜拜：

#include <cstdio>
#include <cstring>
int map[13][2], mtx[5][6], q[5], opt;
void init()
{
    int i, j, n;
    for (i = n = 1; i <= 3; ++i) for (j = 1; j <= 4; ++j, ++n)
        {
            map[n][0] = i;
            map[n][1] = j;
        }
}
int sum(int y, int x)
{
    if (!mtx[y][x]) return 0;
    mtx[y][x] = 0;
    return 1 + sum(y + 1, x) + sum(y - 1, x) + sum(y, x + 1) + sum(y, x - 1);
}
void DFS(int last, int i)
{
    if (i < 5)
    {
        while (++last <= 12)
        {
            q[i] = last;
            DFS(last, i + 1);
        }
    }
    else
    {
        memset(mtx, 0, sizeof mtx);
        for (i = 0; i < 5; ++i) mtx[map[q[i]][0]][map[q[i]][1]] = 1;
        if (sum(map[q[0]][0], map[q[0]][1]) == 5) ++opt;
    }
}
int main()
{
    init();
    DFS(0, 0);
    printf("%d", opt);
    return 0;
}