我讨厌起名字

用户名：jeffrey222

访问量：8112

签　名：

等　　级
排　　名	6720
经　　验	1384
参赛次数	1
文章发表	8
年　　龄	0
在职情况	学生
学　　校	合工大
专　　业	信息计

　　自我简介：

编程小菜鸡

TA的其他文章

分糖果-通俗的方法(C++代码)
浏览：1175

剪格子-DFS+迭代加深搜索(C++描述，错25%的进来看)
浏览：1376

危险系数DFS处理方法-题解(C++代码)
浏览：820

你可能喜欢

九宫重排，编码+BFS （C++代码）

　　作者: 我讨厌起名字　　　　发表时间：2020-02-12 20:24:53 浏览：855　|　评论：0　

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

**ID映射的思想来源于刘汝佳《算法竞赛入门》**
**在该网站提交时间超限33%，但在蓝桥官方练习网站正确运行**
**今天又向后学了一点，发现在《算法竞赛入门》7.5节 路径寻找问题 有一道一模一样的原题。**

------------

```cpp
#include<iostream>
#include<cstring>
#include<queue>
#include<vector>
#include<map>
using namespace std;

map<string,int> idcache;
vector<string> scache;
int father[1000000]; //父节点 
queue<int> q;
string start,tail;

int id(string s)
{
	if(idcache.count(s)) return idcache[s];
	scache.push_back(s);
	idcache[s] = scache.size()-1;
	return idcache[s];
}

string Swap(const string s,int i,int j)
{   //交换i j位 
	string s1(s);
	char c;
	c=s1[i];s1[i]=s1[j];s1[j]=c;
	return s1;
}

bool bfs()
{
	int i,j;
	bool ok;
	int record,tempcord; 
	string s,s2;
	while(!q.empty())
	{
		record = q.front();
		s=scache[record];
		q.pop();
		j=s.find('.');
		if(j-1>=0 && j!=3 && j!=6)
		{
			ok=true;
			s2=Swap(s,j,j-1);	
			if(idcache.count(s2)) ok=false;
			if(id(s2) == id(tail)){
				father[id(s2)] = record;
				return true;
			} 			
			if(ok){
				tempcord=id(s2);
				father[tempcord] = record;
				q.push(tempcord);
			}
		}
		
		if(j-3>=0)
		{
			ok=true;
			s2=Swap(s,j,j-3);	
			if(idcache.count(s2)) ok=false;
			if(id(s2) == id(tail)){
				father[id(s2)] = record;
				return true;
			} 
			if(ok){
				tempcord=id(s2);
				father[tempcord] = record;
				q.push(tempcord);
			}
		}
		if(j+1<9 && j!=2 && j!=5)
		{
			ok=true;
			s2=Swap(s,j,j+1);	
			if(idcache.count(s2)) ok=false;
			if(id(s2) == id(tail)){
				father[id(s2)] = record;
				return true;
			} 
			if(ok){
				tempcord=id(s2);
				father[tempcord] = record;
				q.push(tempcord);
			}
		}
		if(j+3<9)
		{
			ok=true;
			s2=Swap(s,j,j+3);	
			if(idcache.count(s2)) ok=false;
			if(id(s2) == id(tail)){
				father[id(s2)] = record;
				return true;
			} 
			if(ok){
				tempcord=id(s2);
				father[tempcord] = record;
				q.push(tempcord);
			}
		}
	}
	return false;
}

int main()
{
	int length=0,t;
	cin>>start>>tail;
	q.push(id(start));
	father[id(start)] = -1;
	id(tail);
	if(bfs()){
		t=father[id(tail)];
		while(t!=-1){
			t=father[t];
			length++;
		} 
		cout<<length;
	}
	else cout<<-1;
}
```

0.0分

3 人评分

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

我讨厌起名字

TA的其他文章

你可能喜欢

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

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

C二级辅导-进制转换（C++代码）

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

剪格子（C语言代码）

九宫重排，编码+BFS （C++代码）

评论区

精彩推荐

回文数字（C++代码）

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

剔除相关数（C语言代码）

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

拆分位数（C语言代码）

求组合数（C语言代码）

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

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

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

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

我讨厌起名字

TA的其他文章

你可能喜欢

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

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

C二级辅导-进制转换 （C++代码）

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

剪格子 （C语言代码）

九宫重排，编码+BFS （C++代码）

评论区

精彩推荐

回文数字 （C++代码）

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

剔除相关数 （C语言代码）

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

拆分位数 （C语言代码）

求组合数 （C语言代码）

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

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

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

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

C二级辅导-进制转换（C++代码）

剪格子（C语言代码）

　　评论区

回文数字（C++代码）

剔除相关数（C语言代码）

拆分位数（C语言代码）

求组合数（C语言代码）

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