JakeLin

用户名：jake546

访问量：43185

签　名：

腾讯需要我！

等　　级
排　　名	40
经　　验	13199
参赛次数	3
文章发表	85
年　　龄	21
在职情况	学生
学　　校	华南农业大学
专　　业

　　自我简介：

幸福是奋斗出来的

TA的其他文章

JakeLin-2086题-最长公共子序列-题解(C/C++代码)-DP（详细解析）
浏览：618

JakeLin-2129题-最长公共子序列-题解(C++代码)-DP
浏览：244

JakeLin-1565题-蓝桥杯算法提高VIP-质数的后代-题解(C++代码)
浏览：451

你可能喜欢

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

JakeLin-题解1426：蓝桥杯历届试题-九宫重排（C++代码）

　　作者: JakeLin　　　　发表时间：2020-02-07 20:26:56 浏览：536　|　评论：0　

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

```cpp
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<set>
using namespace std;
struct Node{   //为一个九宫格的状态 
	char s[3][3]; //九宫序列 
	int x,y; //.的横纵坐标 
	int d;  //步数：从初始状态转变d次 
};
set<string> vis;  //记录该状态是否访问过 
int dx[] = {-1,1,0,0};
int dy[] = {0,0,-1,1};
bool ok=false;
bool bfs(Node* start,Node* end){
	queue<Node*> q;
	q.push(start);
	vis.insert(*start->s);  //*二维数组 => 一维数组  => string 
	while(!q.empty()){
		Node* u = q.front();
		q.pop();
		if(strcmp(*u->s,*end->s)==0){     //该状态是终态 
			cout<<u->d;   //输出该状态的步数 
			ok = true;
			return true;
		}
		int ux = u->x;   //.的位置（ux，uy） 
		int uy = u->y;
		int ud = u->d;
		for(int i=0;i<4;i++){  //.可向四个方向移动 
			int newx = ux + dx[i];   //.向四个方向移动  
			int newy = uy + dy[i];
			if(newx>=0 && newx<3 && newy>=0 && newy<3){
				Node* newn = new Node();   //新建一个状态 
				newn->d = ud + 1;  //它的步数是出队的状态+1 
				newn->x = newx;  //它的.的位置是（newx,newy） 
				newn->y = newy;
				strcpy(*newn->s,*u->s);   //它的序列先跟出队的状态一样 
				newn->s[ux][uy] = newn->s[newx][newy];  //.与四个方向响铃的数字交换 
				newn->s[newx][newy]='.';
				if(!vis.count(*newn->s)){  //如果这个状态(节点)合法 
					vis.insert(*newn->s);  // 访问这个状态 
					q.push(newn);
				}
			}
		}
	}
	if(!ok){
		cout<<"-1";
		return false;
	}
	
}
int main(){
	Node* start = new Node();
	Node* end = new Node();
	char t;
	for(int i=0;i<3;i++){ //输入初始状态
		for(int j=0;j<3;j++){
			cin>>t;
			start->s[i][j]=t;
			if(t=='.'){
				start->x=i;
				start->y=j;
			}
		}
	}
	getchar(); //接收回车
	for(int i=0;i<3;i++){ //输入结束状态
		for(int j=0;j<3;j++){
			cin>>t;
			end->s[i][j]=t;
			if(t=='.'){
				end->x=i;
				end->y=j;
			}
		}
	}
	start->d=0;
	bfs(start,end);
	return 0;
}
```

0.0分

5 人评分

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

JakeLin

TA的其他文章

你可能喜欢

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

C二级辅导-公约公倍（C语言代码）

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

时间转换（Java代码）

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

JakeLin-题解1426：蓝桥杯历届试题-九宫重排（C++代码）

评论区

精彩推荐

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

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

蚂蚁感冒（C语言代码）

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

分糖果（C语言代码）

敲七（C++代码）

敲七（C语言代码）

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

盐水的故事（C语言代码）

简单的a+b （C语言代码）

JakeLin

TA的其他文章

你可能喜欢

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

C二级辅导-公约公倍 （C语言代码）

C语言训练-求矩阵的两对角线上的元素之和 （C语言代码）

时间转换 （Java代码）

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

JakeLin-题解1426：蓝桥杯历届试题-九宫重排 （C++代码）

评论区

精彩推荐

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

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

蚂蚁感冒 （C语言代码）

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

分糖果 （C语言代码）

敲七 （C++代码）

敲七 （C语言代码）

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

盐水的故事 （C语言代码）

简单的a+b （C语言代码）

C二级辅导-公约公倍（C语言代码）

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

时间转换（Java代码）

JakeLin-题解1426：蓝桥杯历届试题-九宫重排（C++代码）

　　评论区

蚂蚁感冒（C语言代码）

分糖果（C语言代码）

敲七（C++代码）

敲七（C语言代码）

盐水的故事（C语言代码）