万物皆可Floyd

用户名：chx123456

访问量：473

签　名：

等　　级
排　　名	72112
经　　验	168
参赛次数	1
文章发表	1
年　　龄	0
在职情况	学生
学　　校	及导师
专　　业

　　自我简介：

TA的其他文章

蓝桥杯历届试题-九宫重排-题解(C++代码)
浏览：300

你可能喜欢

2006年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

蓝桥杯历届试题-九宫重排-题解(C++代码)

　　作者: 万物皆可Floyd　　　　发表时间：2020-01-21 20:20:59 浏览：300　|　评论：0　

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

#include<iostream> 
#include<string.h> 
#include<queue>
#include<map>
 
using namespace std;
char start[4][4],goal[4][4];
int df[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
map<string,int> vis;
struct Node
{
    int x,y;
    long long step;
    char Map[4][4];
};
bool check_g(Node a)///判断这个图和目标图是否相同
{
    for(int i=1;i<=3;i++)
     for(int j=1;j<=3;j++)
      if(a.Map[i][j]!=goal[i][j])return false;
    return true;
}
bool check_cf(Node a)///判断这个局面是否出现过
{
    string s = "";
    for(int i=1;i<=3;i++)
     for(int j=1;j<=3;j++)s+=a.Map[i][j];
    if(vis[s]>0)return false;
    vis[s]++;
    return true;
}
int BFS(int x1,int y1)///BFS寻找最少步数
{
    Node cur,next;
    cur.x = x1;cur.y = y1;
    cur.step = 0;
    for(int i=1;i<=3;i++)
      for(int j=1;j<=3;j++)
        cur.Map[i][j] = start[i][j];//复制一份状态
    queue<Node> Q;//创建一个队列
    Q.push(cur); //加入队列
    if(check_g(cur)) return cur.step;//检查是否为目标状态
    while(!Q.empty()){
        cur = Q.front();
        Q.pop();    // 出队列
        for(int i=0;i<4;i++){
            next.x = cur.x + df[i][0];
            next.y = cur.y + df[i][1];
             for(int i1=1;i1<=3;i1++)
              for(int j=1;j<=3;j++)
               next.Map[i1][j]= cur.Map[i1][j];//复制一份状态
            next.step = cur.step + 1;//当前 步数加一
            if(next.x>=1&&next.x<=3&&next.y>=1&&next.y<=3){//边界内
                swap(next.Map[next.x][next.y],next.Map[cur.x][cur.y]);///交换两个方格的位置；
                if(check_cf(next)){//检查重复
                    if(check_g(next)) return next.step;//检查是否为目标状态
                   Q.push(next);//入队列
                }
            }
        }
    }
    return -1;
}
int main()
{
    int x1,y1;
    for(int i=1;i<=3;i++)
      for(int j=1;j<=3;j++){
            cin>>start[i][j];
            if(start[i][j]=='.') x1=i,y1=j;///记录空白格的位置
        }
    for(int i=1;i<=3;i++)
       for(int j=1;j<=3;j++)
            cin>>goal[i][j];
    cout<<BFS(x1,y1)<<endl;
    return 0;
}

0.0分

0 人评分

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

　　评论区

精彩推荐

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

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

WU-输入输出格式练习（C++代码）

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

蚂蚁感冒（C语言代码）

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

1052题解（链表操作）

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

【偶数求和】（C语言代码）

很简单，，题解1041：C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

万物皆可Floyd

TA的其他文章

你可能喜欢

printf基础练习2 （C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

字符串的输入输出处理（C语言代码）

简单编码（C++代码）

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

蓝桥杯历届试题-九宫重排-题解(C++代码)

评论区

精彩推荐

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

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

WU-输入输出格式练习（C++代码）

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

蚂蚁感冒（C语言代码）

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

1052题解（链表操作）

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

【偶数求和】（C语言代码）

很简单，，题解1041：C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

万物皆可Floyd

TA的其他文章

你可能喜欢

printf基础练习2 （C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

字符串的输入输出处理 （C语言代码）

简单编码 （C++代码）

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

蓝桥杯历届试题-九宫重排-题解(C++代码)

评论区

精彩推荐

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

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

WU-输入输出格式练习 （C++代码）

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

蚂蚁感冒 （C语言代码）

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

1052题解（链表操作）

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

【偶数求和】 （C语言代码）

很简单，，题解1041：C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

字符串的输入输出处理（C语言代码）

简单编码（C++代码）

　　评论区

WU-输入输出格式练习（C++代码）

蚂蚁感冒（C语言代码）

【偶数求和】（C语言代码）