$\color{green}{<–画图不易,点下这里赞一下吧}$
解题思路
暴力穷举。穷举出所有给定序列通过交换能得到的新序列,在穷举过程中保存交换次数。
在穷举过程中,如果出现了结果序列,就输出交换次数。
否则不能得到结果序列,输出 -1。
图解举例
起始状态: 为 1 2 3 x 4 6 7 5 8
交换一次:
- x 与上方元素交换得到:
x 2 3 1 4 6 7 5 8
- x 与右方元素交换得到:
1 2 3 4 x 6 7 5 8
- x 与下方元素交换得到:
1 2 3 7 4 6 x 5 8
交换两次得到:
2 x 3 1 4 6 7 5 8
1 x 3 4 2 6 7 5 8
1 2 3 4 6 x 7 5 8
1 2 3 4 5 6 7 x 8
1 2 3 7 4 6 5 x 8
交换三次得到:
2 3 x 1 4 6 7 5 8
- .....
1 2 3 4 5 6 7 8 x
- .....
得到了最终结果,输出 3.
算法思路
- 用一个队列保存当前获得的序列
- 用一个哈希表保存各个序列与对应额交换次数。
- 从队列中取出队头这个序列,计算出这个序列通过交换能得到的序列。如果能到得的序列是个新序列(哈希表中没有这个序列),就把这个新序列放入队尾,哈希表中记录新序列对应的交换次数。
- 如果在上述过程中得到了结果序列,则输出交换次数,结束。
- 如果最终没有得到结果序列。输出-1。
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <queue>
using namespace std;
// 保存各个序列
queue<string> q;
string s;
// 保存序列与对应的交换次数
unordered_map<string, int> h;
int main()
{
// 输入原始序列
for(int i = 1; i <= 9; i++)
{
char c;
cin >> c;
s += c;
}
// 保存初始状态
h[s] = 0;
q.push(s);
// 定义上下左右四个交换方向
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
// 依次进行交换
while(!q.empty())
{
// 获得当前序列
string t = q.front();
q.pop();
// 如果是最后结果,输出答案
if(t == "12345678x")
{
cout << h[t] << endl;
return 0;
}
// 找到 x 的位置
int pos = t.find('x');
// 计算 x 的坐标
int a = pos /3 , b = pos % 3 ;
// 获取当前序列对应的交换次数
int dist = h[t];
// 尝试和四个方向的元素进行交换
for(int i = 0; i < 4; i++)
{
int x = a + dx[i], y = b + dy[i];
// 判断是否越界
if(x >= 0 && x <= 2 && y >= 0 && y <= 2)
{
// 交换
swap(t[pos], t[3 * x + y]);
// 如果是个新序列,就保存新序列和对应的交换次数
if(h.find(t) == h.end())
{
h[t] = dist + 1;
q.push(t);
}
// 恢复现场,进行下一个方向的交换
swap(t[pos], t[3 * x + y]);
}
}
}
// 没有得到结果序列,输出-1
cout << -1;
return 0;
}
比较关键的一点:
一维坐标映射到二维 -> (x / n, x % n )
二维映射一维 -> x * n + y
if(h.find(t) == h.end())
不懂
如果在unordered_map中找不到t,就会固定返回h.end()
umap.end() 返回指向容器中最后一个键值对之后位置的正向迭代器,相当于迭代器来到了,unorder_map 的最后一个对象的索引位置。
find() 输入容器的键 如果找到返回一个迭代器 否则返回末尾end() 就是说没找到的话返回end() 就进入if句
有个疑问就是unordered_map[HTML_REMOVED] h初始化的时候哈希值都是0吗?没发现对其哈希值初始化的操作啊
是的,没有的元素,为0
海绵宝宝我爱你
大佬,为啥不能把h.find(t) == h.end()并入越界判断条件中呢?
没交换怎么判断是不是新序列
感谢大佬解题与代码分享~
图很棒~
大佬的图实在是太棒了,感谢大佬