蓝桥杯-【剪邮票】【2016年省赛B组题解】--bfs+全排列

剪邮票

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

蓝桥杯-【剪邮票】【2016年省赛B组题解】--bfs+全排列

 

 

现在你要从中剪下5张来,要求必须是连着的。
(仅仅连接一个角不算相连)
比如,【图2.jpg】,【图3.jpg】中,粉红色所示部分就是合格的剪取。

蓝桥杯-【剪邮票】【2016年省赛B组题解】--bfs+全排列

 

 

 

蓝桥杯-【剪邮票】【2016年省赛B组题解】--bfs+全排列

 

 

 

请你计算,一共有多少种不同的剪取方法。
请填写表示方案数目的整数。
注意:你提交的应该是一个整数,不要填写任何多余的内容或说明性文字。
 

思路:用数组b[ ]生成12个位置的全排列,然后把数组b赋值给数组map

          然后深搜判断连通性,如果连通性为1,满足

答案: 116

代码:

#include<iostream>
#include<stdio.h>
#include<algorithm> 
#include<string.h>
using namespace std;
int a[12]={0,0,0,0,0,0,0,1,1,1,1,1};
int map[3][4];
int visit[3][4];
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
void dfs(int x,int y){
    visit[x][y] = 1;
    for(int i=0;i<4;i++){
        int xx = x+dx[i];
        int yy = y+dy[i];
        if(xx<0||xx>=3||yy<0||yy>=4)
            continue;
        if(map[xx][yy]&&!visit[xx][yy]){
            dfs(xx,yy);
        }
    }
}
int main(){
    int ans = 0;
    do{
        int cnt = 0; 
        memset(map,0,sizeof(map));
        for(int i=0;i<3;i++){
            for(int j=0;j<4;j++){
                map[i][j] = a[cnt++];
                visit[i][j] = 0; 
            }
        }
        int t=0;
        for(int i=0;i<3;i++){
            for(int j=0;j<4;j++){
                if(map[i][j]==1&&!visit[i][j]){
                    t++;
                    dfs(i,j);
                }
            }
        }
        if(t==1) ans++;
    }while(next_permutation(a,a+12));
    cout<<ans<<endl;
    return 0;
}

 

上一篇:关于点双和边双的求法


下一篇:用三种不同颜色表示的三个决策边界