题目考点：STL、 bfs题目大意：可以看成x上下左右移动最终复原八数码。题目分析：普通的bfs，不过是用map<string, int>储存状态（这里用的unorderedmap，比较快）（由于用字符串储存，速度会慢很多，建议改用map<int, int>储存，这里就偷懒了
展开全文
题目描述 在一个3×3的网格中，1~8这8个数字和一个“X”恰好不重不漏地分布在这3×3的网格中。 例如： 1 2 3
X 4 6
7 5 8在游戏过程中，可以把“X”与其上、下、左、右四个方向之一的数字交换（如果存在）。 我们的目的是通过交换，使得网格变为如下排列（称为正确排列）： 1 2 3
4
展开全文
#include<iostream>
#include<algorithm>
#include<map>
#include<queue>;
using namespace std;
const int N = 363000;
string s = ""
展开全文
思路方法：
题目大意是输入的33矩阵能否移动空格'x'来和目标矩阵一样，这里我们直接比较33矩阵比较麻烦，不妨直接将他们化为字符串来直接比较，这样一来我们会有很多个字符串状态，我是通过map的方式来存每个字符串的编号以及一个映射字符串数组来记录每个编号的字符串，最重要的是采用bfs来进行搜索看每个状
展开全文
题目让我们求出将八数码复原的最小步数并且输出出具体方案，这是一道搜索题，因为数据范围很小。但是这道题可以借助两个算是比较高级的知识来优化，A* 算法和康托展开，A*是因为加入评估函数后可以大大的加快搜索速度。这道题的评估函数便是每个数当前所在位置和那个数最终所在位置的曼哈顿距离总和。而这里因为棋盘上
展开全文
关于看了他人提交后发现内存和时间比我远小一个数量级，不服输的我花了几个小时终于优化成功！！！
将string进行hash可以极大提升速度和降低开销；
为了方便转换，我将题中的'x'替换为'0'（本题刚好用不到0这个数字，可以用来替代！），可以方便相互转换；
注意数字转回字符串时，'0'开头的字符串
展开全文
emmm，其实也不算很难的思路，就是用mp去重并记录走过的路径，就ok了这道题，只需要一个记录路径的mp就行了，map多了会爆内存（别问我是怎么知道的qaq），对了，还有就是二维一维坐标相互转换的方法，最顶上三个函数就是了。
#include<bits/stdc++.h>
using n
展开全文
#include<bits/stdc++.h>
using namespace std;
const int N=363000;
string st[N];
unordered_map<string,int > mp;
int last[N];
bool used[N];/
展开全文
核心思路：bfs+康托展开去重关于康托展开：康托展开的公式如下：k=a[n](n-1)!+a[n-1](n-2)!+....+a[1]0!;康托展开主要解决的是全排列的状态储藏问题，k指的是当前这个数在全排列中由小到大排第k个。其中的a[n]指的是当前这个数位上的数字在还没出现的数字中比他小的数有几
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
