2016年蓝桥杯省赛A组c++第7题(图论)

/*
有12张连在一起的12生肖的邮票,规格是3*4，即：
1111
1111
1111 
现在你要从中剪下5张来，要求必须是连着的。（仅仅连接一个角不算相连）
*/

/*
思路：
先将所有五个一组的情况遍历，然后用广度优先判断是否连通。
*/ 

#include<cstdio>  
#include<cstring>  
#include<algorithm>  
#include<iostream>  
#include<string>  
#include<vector>  
#include<stack>  
#include<bitset>  
#include<cstdlib>  
#include<cmath>  
#include<set>  
#include<list>  
#include<deque>  
#include<map>  
#include<queue>  
using namespace std;  

int a[12]= {1,2,3,4,6,7,8,9,11,12,13,14};//邮票数组 
int vis[20];  //规格：4*5
/*
在逻辑上可以将vis数组看成： 
01 02 03 04 00 
06 07 08 09 00 
11 12 13 14 00
00 00 00 00 00 
*/

int main()  
{  
int sum=0;  //可行解的总数
for(int i1=0; i1<12; i1++)  
for(int i2=i1+1; i2<12; i2++)  
for(int i3=i2+1; i3<12; i3++)  
for(int i4=i3+1; i4<12; i4++)  
for(int i5=i4+1; i5<12; i5++)  
                    {  
                        memset (vis,0,sizeof(vis));  //每次验证一个解是否可行之前先将标志数组初始化 
int p=0;  //当前解的连通度 
                        vis[a[i1]]=1;  //a[]是邮票数组 
                        vis[a[i2]]=1;  
                        vis[a[i3]]=1;  
                        vis[a[i4]]=1;  
                        vis[a[i5]]=1;  

                        queue<int>q;  //声明一个队列q 
                        q.push(a[i1]);  //初始节点入队 
                        vis[a[i1]]=0;  //入队节点的对应的标志归零 
while(!q.empty())  
                        {  
int top=q.front();  
                            q.pop();  
                            p++;  
if(vis[top+1]) { q.push(top+1);vis[top+1]=0; }  //验证右连通 
if(vis[top+5]) { q.push(top+5);vis[top+5]=0; }  //验证下连通
if(vis[top-1]) { q.push(top-1);vis[top-1]=0; }  //验证左连通
if(vis[top-5]) { q.push(top-5);vis[top-5]=0; }  //验证上连通
                        }  
if(p==5)  //全连通时p==5 
                        {  
                            sum++;  
                            cout<<a[i1]<<" "<<a[i2]<<" "<<a[i3]<<" "<<a[i4]<<" "<<a[i5]<<endl;  
                        }  
                    }  

    cout<<sum<<endl;  
return 0;  
} 

 

 

 

 

tz@COI HZAU

2018/3/16