剪邮票 深搜+标记 【蓝桥真题】(c++实现)

题目描述:

如【图1.jpg】, 有12张连在一起的12生肖的邮票。
在这里插入图片描述
现在你要从中剪下5张来,要求必须是连着的。
(仅仅连接一个角不算相连)
比如,【图2.jpg】,【图3.jpg】中,粉红色所示部分就是合格的剪取。
在这里插入图片描述
在这里插入图片描述
请你计算,一共有多少种不同的剪取方法。

请填写表示方案数目的整数。

注意:你提交的应该是一个整数,不要填写任何多余的内容或说明性文字。

我的思路

  • 本题有两种思路,一是用深度搜索查找五个块然后判断是否是连通块,二是枚举这些块中的五个,判断是否是连通块,本题采用两种结合,类深搜方式查找并记录。
  • 在深搜查找12个块时,利用标记数组vis标记出12个中的取五个块的组合,然后判断该组合是否是连通块,是则记录,判断连通块的方式是从第一个块向四周查找,看是否存在相邻块,有则即记录相邻块数,然后查找相邻块,如果查找到最后结果为5代表成功找到。

算法展示

#include <cstdio>
#include <cstring>
int cav[13][2], vis[5][6], org[5], ans;//org组合数,vis标记数组,cav默认邮票表格 
//判断是否连通 
int is_cir(int y, int x){    
    //如果该标记点不存在,结束        
    if (!vis[y][x]) return 0;
    vis[y][x] = 0;
    //得到所有连通块数量 
    return 1 + is_cir(y + 1, x) + is_cir(y - 1, x) + is_cir(y, x + 1) + is_cir(y, x - 1);
}

void DFS(int last, int i){
    if (i < 5){
        // 查找所有邮票表格
        while (++last <= 12){
            org[i] = last;
            DFS(last, i + 1);
        }
    }
    else{
        
        memset(vis, 0, sizeof vis);//初始化为0,即未访问
        //生成一种组合 
        for (i = 0; i < 5; ++i) vis[cav[org[i]][0]][cav[org[i]][1]] = 1;
        //判断该组合是否满足连通 
        if (is_cir(cav[org[0]][0], cav[org[0]][1]) == 5) ++ans;
    }
}

int main() {
    // 初始化cav,[n][0]代表行数,[n][1]代表值,n代表所有格子 
    int i, j, n;
    for (i = n = 1; i <= 3; ++i) 
    {
        for (j = 1; j <= 4; ++j, ++n)
        {
            cav[n][0] = i; cav[n][1] = j;
        }
    } 
    //
    DFS(0, 0);
    printf("%d", ans);
    return 0;
}

上文链接:方格填数 全排列+你想不到的判断 【蓝桥杯真题】(c++实现)

评论

暂无评论