蓝桥剪邮票（dfs+bfs）

心已赠人 2022-06-18 11:45 162阅读 0赞

思路来自http://blog.csdn.net/xunalove/article/details/68935661

如【图1.jpg】, 有12张连在一起的12生肖的邮票。  
现在你要从中剪下5张来，要求必须是连着的。  
（仅仅连接一个角不算相连）  
比如，【图2.jpg】，【图3.jpg】中，粉红色所示部分就是合格的剪取。  
  
  
请你计算，一共有多少种不同的剪取方法。  
  
  
请填写表示方案数目的整数。

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

![Center][]

先深搜出点，转成2维地图形式，然后广搜判断点是否是相连的

#include<iostream>
    #include<cmath>
    #include<string.h>
    #include<queue>
    #include<algorithm>
    using namespace std;
    int a[12],v[12]={0},cnt=0;
    int dir[4][2]={-1,0,0,-1,0,1,1,0};
    struct st
    {
    	int x;
    	int y;
    }s;
    queue<struct st> Q;
    int bfs()
    {
    	int map[3][4]={0},x,y,i,j,k=0,xx,yy;
    	for (i=0; i<12; i++)//map为1是选择的点，为0 不是
    	{
    		if (a[i] != -1)
    		{
    			x = a[i]/4;  
    			y = a[i]%4;
    			map[x][y] = 1;
    		}
    	}
    	//搜索相邻的
    	s.x = x;
    	s.y = y;
    	map[s.x][s.y] = 0;
    	Q.push(s);
    	while (!Q.empty())
    	{
    		s = Q.front();
    		Q.pop();
    		for (i=0; i<4; i++)
    		{
    			xx = dir[i][0]+s.x;
    			yy = dir[i][1]+s.y;
    			if (xx>=0&&yy>=0&&xx<3&&yy<4&&map[xx][yy]!=0)
    			{
    				k++;
    				struct st temp;
    				temp.x = xx;
    				temp.y = yy;
    				map[xx][yy] = 0;
    				Q.push(temp);
    			}
    		}
    	}
    	if (k >= 4)
    	{
    		return 1;
    	}
    	return 0;
    }
    void dfs(int x,int y)
    {
    	int i,j;
    	if (x == 5)
    	{
    		if (bfs())
    		{
    			cnt++;
    		}
    		return ;
    	}
    	for (i=y; i<12; i++)
    	{
    		if (!v[i])
    		{
    			v[i] = 1;
    			a[x] = i;
    			dfs(x+1,i);
    			a[i] = -1;
    			v[i] = 0;
    		}
    	}
    }
    int main()
    {
    	memset(a,-1,sizeof(a));
    	dfs(0,0);
    	cout<<cnt;
    }

[Center]: /images/20220618/a53c169469e84b2bafb2fc08c78d71be.png