剪邮票(bfs + dfs)别人的
本文最后更新于 1803 天前,其中的信息可能已经有所发展或是发生改变。
#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;
}
作者:Yuyy
博客:https://yuyy.info
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇