道尽似空

用户名：dengmouren

访问量：3893

签　名：

等　　级
排　　名	11326
经　　验	1035
参赛次数	0
文章发表	7
年　　龄	0
在职情况	学生
学　　校	重庆邮电大学
专　　业

　　自我简介：

TA的其他文章

信息学奥赛一本通T1252-走迷宫-题解（C++代码）看我这一个就学会bfs最基础的了
浏览：1246

你可能喜欢

蓝桥杯历届试题-九宫重排（C++代码）使用了c++STL 目前这个解法是该网站最好的

　　作者: 道尽似空　　　　发表时间：2020-01-17 10:59:23 浏览：362　|　评论：0　

原题链接：蓝桥杯历届试题-九宫重排

#include "iostream"
    #include "algorithm"
    #include "vector"
    #include "set"
    #include "string.h"
    #include "ctype.h"
    #define M 1000000
    using namespace std;
    typedef int type[9];
    type qs[M];
    type mb;
    int front,rear;
    int dir[4][2]={-1,0,0,-1,0,1,1,0};
    int dis[M]={0};
    set<int> vis; //容器，存储不同的值
    int panchong(int x)
    {
        int i,sum=0;
        for (i=0; i<9; i++)
        {
            sum = sum*10+qs[x][i];
        }
        if (vis.count(sum)) //容器中有相同
        {
            return 0;
        }
        vis.insert(sum);//插入容器
        return 1;
    }
    int bfs()
    {
        front = 1;
        rear = 2;
        int i,k=0,x,y,xx,yy;
        while (front < rear)
        {
            type &s = qs[front]; //s指向qs[front]
            if (memcmp(s,mb,sizeof(mb)) == 0)
            {
                return front;
            }
            for (k=0; k<9; k++)
            {
                if (s[k]==0)
                    break;
            }
            x = k/3;
            y = k%3; // 转成二维数组
            for (i=0; i<4; i++)
            {
                xx = x+dir[i][0];
                yy = y+dir[i][1];
                if(xx>=0 && xx<3 && yy>=0 && yy<3)
                {
                    type &t = qs[rear];//t指向qs[rear]
                    memcpy(t,s,sizeof(s));
                    t[k] = s[xx*3+yy]; //交换空格与数字位置
                    t[xx*3+yy] = s[k];
                    if (panchong(rear))//得到新的图进行判断重复
                    {
                        dis[rear] = dis[front]+1;
                        rear++;
                    }
                }
            }
            front++;
        }
        return -1;
    }
    int main()
    {
        int i,cnt;
        char ch[10],ch2[10];
        scanf("%s%s",ch,ch2);
        for (i=0; i<9; i++)
        {
            ch[i]<='8'&&ch[i]>='0' ? qs[1][i]=ch[i]-'0' : qs[1][i]=0;
        }
        for (i=0; i<9; i++)
        {
            ch2[i]<='8'&&ch2[i]>='0' ? mb[i]=ch2[i]-'0' : mb[i]=0;
        }
        cnt = bfs();
        if(cnt>0)
        {
            cout<<dis[cnt]<<endl;
        }
        else
        {
            cout<<-1<<endl;
        }
        return 0;
    }
    
    
	
	
c++优秀算法

0.0分

4 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

精彩推荐

【出圈】（C语言代码）

A+B for Input-Output Practice (IV) （C语言代码）

【亲和数】（C语言代码）

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

DNA （C语言代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

C二级辅导-统计字符（C语言代码）

字符逆序（C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

1392题解(大数相加)

道尽似空

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

【计算两点间的距离】（C语言代码）

逆反的01串（C++代码）（依旧推荐switch）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

蓝桥杯历届试题-九宫重排（C++代码）使用了c++STL 目前这个解法是该网站最好的

评论区

精彩推荐

【出圈】（C语言代码）

A+B for Input-Output Practice (IV) （C语言代码）

【亲和数】（C语言代码）

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

DNA （C语言代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

C二级辅导-统计字符（C语言代码）

字符逆序（C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

1392题解(大数相加)

道尽似空

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

【计算两点间的距离】 （C语言代码）

逆反的01串 （C++代码）（依旧推荐switch）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

蓝桥杯历届试题-九宫重排 （C++代码）使用了c++STL 目前这个解法是该网站最好的

评论区

精彩推荐

【出圈】 （C语言代码）

A+B for Input-Output Practice (IV) （C语言代码）

【亲和数】 （C语言代码）

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

DNA （C语言代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

C二级辅导-统计字符 （C语言代码）

字符逆序 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

1392题解(大数相加)

【计算两点间的距离】（C语言代码）

逆反的01串（C++代码）（依旧推荐switch）

蓝桥杯历届试题-九宫重排（C++代码）使用了c++STL 目前这个解法是该网站最好的

　　评论区

【出圈】（C语言代码）

【亲和数】（C语言代码）

C二级辅导-统计字符（C语言代码）

字符逆序（C语言代码）