蓝桥杯 2016省赛 C/C++ A T7

知识点

全排列+dfs连通块检测

题目

剪邮票

如【图1.jpg】, 有12张连在一起的12生肖的邮票。
现在你要从中剪下5张来，要求必须是连着的。
（仅仅连接一个角不算相连）
比如，【图2.jpg】，【图3.jpg】中，粉红色所示部分就是合格的剪取。

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

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

思路

本题考虑全排列问题，可以通过递归+回溯或者next_permutation()生成全排列，然后通过检测连通块个数（dfs）判断是否合格。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int ans = 0;

void dfs(int g[3][4],int i,int j)
{
    g[i][j]=0;
    if (i+1<=2 && g[i+1][j]==1) dfs(g,i+1,j);
    if (i-1>=0 && g[i-1][j]==1) dfs(g,i-1,j);
    if (j+1<=3 && g[i][j+1]==1) dfs(g,i,j+1);
    if (j-1>=0 && g[i][j-1]==1) dfs(g,i,j-1);
}

bool check(int arr[12])
{
    int g[3][4];
    memset(g,0,sizeof(g));
    for (int i=0;i<3;i++)
        for (int j=0;j<4;j++)
            if (arr[i*4+j]==1)
                g[i][j]=1;
    int cnt=0;
    for (int i=0;i<3;i++)
        for (int j=0;j<4;j++)
            if (g[i][j]==1)
            {
                dfs(g,i,j);
                cnt++;
            }
    return cnt==1;
}

int main()
{
    int per[]={0,0,0,0,0,0,0,1,1,1,1,1};
    do {
        if (check(per))
            ans++;
    } while(next_permutation(per,per+12));
    cout << ans << endl;
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int a[] = {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1};//它的每个排列代表着12选5的一个方案
int ans = 0;

void dfs(int g[3][4],int i,int j)
{
    g[i][j]=0;
    if (i+1<=2 && g[i+1][j]==1) dfs(g,i+1,j);
    if (i-1>=0 && g[i-1][j]==1) dfs(g,i-1,j);
    if (j+1<=3 && g[i][j+1]==1) dfs(g,i,j+1);
    if (j-1>=0 && g[i][j-1]==1) dfs(g,i,j-1);
}

bool check(int arr[12])
{
    int g[3][4];
    memset(g,0,sizeof(g));
    for (int i=0;i<3;i++)
        for (int j=0;j<4;j++)
            if (arr[i*4+j]==1)
                g[i][j]=1;
    int cnt=0;
    for (int i=0;i<3;i++)
        for (int j=0;j<4;j++)
            if (g[i][j]==1)
            {
                dfs(g,i,j);
                cnt++;
            }
    return cnt==1;
}

bool vis[12];

void f(int k, int path[12])
{
    if (k==12)
    {
        if (check(path))
        {
            ans++;
            return;
        }
    }
    for (int i=0;i<12;i++)
    {
        if (i>0 && a[i]==a[i-1]&&!vis[i-1]) continue; //现在准备选取的元素和上一个元素相同，但是上一个元素还没被使用
        if (!vis[i])
        {
            vis[i]=true;
            path[k]=a[i];
            f(k+1,path);
            vis[i]=false;
        }
    }
}

int main()
{
    int path[12];
    f(0,path);
    cout << ans << endl;
    return 0;
}