我讨厌起名字

用户名：jeffrey222

访问量：7595

签　名：

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

　　自我简介：

编程小菜鸡

TA的其他文章

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

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

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

你可能喜欢

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

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

　　作者: 我讨厌起名字　　　　发表时间：2020-02-12 20:24:53 浏览：825　|　评论：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语言程序设计教程（第三版）课后习题7.4 （C语言代码）

C语言训练-尼科彻斯定理（C语言代码）。。。内含证明定理

钟神赛车（C语言代码）

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

买不到的数目（C++代码）

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

评论区

精彩推荐

不容易系列（C语言代码）

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

拆分位数（C语言代码）

【简单计算】（C语言代码）

用筛法求之N内的素数。（C语言代码）

关于C语言变量位置的问题

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

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

出圈】指针malloc版

字符串比较（C语言代码）

我讨厌起名字

TA的其他文章

你可能喜欢

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

C语言训练-尼科彻斯定理 （C语言代码）。。。内含证明定理

钟神赛车 （C语言代码）

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

买不到的数目 （C++代码）

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

评论区

精彩推荐

不容易系列 （C语言代码）

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

拆分位数 （C语言代码）

【简单计算】 （C语言代码）

用筛法求之N内的素数。 （C语言代码）

关于C语言变量位置的问题

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

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

出圈】指针malloc版

字符串比较 （C语言代码）

C语言训练-尼科彻斯定理（C语言代码）。。。内含证明定理

钟神赛车（C语言代码）

买不到的数目（C++代码）

　　评论区

不容易系列（C语言代码）

拆分位数（C语言代码）

【简单计算】（C语言代码）

用筛法求之N内的素数。（C语言代码）

字符串比较（C语言代码）