剪邮票（bfs + dfs）别人的

本文最后更新于 1163 天前，其中的信息可能已经有所发展或是发生改变。

代码语言：javascript复制

#include<iostream> 
#include<algorithm>
#include<queue>
#include<cstring>

using namespace std;

int a[100];
int vis[4][5];    //下标为0的不用
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };

int result = 0;

struct node
{
    int x, y;
}s;

void bfs(int a[])
{
    memset(vis, 0, sizeof(vis));   //记得将vis置零，防止有残余的1
    int x, y;

    //把一维下标转换为二维坐标
    for (int i = 1; i <= 5;   i)
    {
        if (a[i] % 4 == 0)
        {
            x = a[i] / 4;
            y = 4;
        }
        else
        {
            x = a[i] / 4   1;
            y = a[i] % 4;
        }
        vis[x][y] = 1;
    }

    s.x = x;
    s.y = y;

    queue<node>Q;
    Q.push(s);
    vis[s.x][s.y] = 0;
    int num = 1;

    node t;
    while (!Q.empty())
    {
        t = Q.front();
        Q.pop();
        
        for (int i = 0; i < 4;   i)
        {
            int xx = t.x   dx[i];
            int yy = t.y   dy[i];
            if (xx >= 1 && xx <= 3 && yy >= 1 && yy <= 4 && vis[xx][yy] == 1)
            {
                  num;    //每有一个相连，num就自增
                vis[xx][yy] = 0;
                s.x = xx;
                s.y = yy;
                Q.push(s);
            }
        }
    }

    if (num == 5)    //如果这5个数都相连    
    {
          result;
    }

}

void dfs(int step)  //从12个数中取出5个（即12取5的所有组合），存入一维数组a中(从下标1开始存储)
{
    if (step == 6)
    {
        bfs(a);        //用bfs判断取出的这5个数在图中是否相连
        return;
    }

    for (int i = 1; i <= 12;   i)
    {
        if (i > a[step - 1])    //以递增的顺序选出，可以防止重复
        {
            a[step] = i;
            dfs(step   1);
        }
    }

    
}

int main()
{
    memset(a, 0, sizeof(a));
    dfs(1);
    cout << result << endl;

    return 0;
}

Post Views: 193

post

0 人点赞