试了试map 会超时 果断用unordered_map
大家其实不用过多去考虑这两个东西
用法类似
时间效率 unordered_map 好于 map 几倍
#include<bits/stdc++.h>
#include<queue>
#include<map>
using namespace std;
const int N =1e6+10;
string end_s="12345678x"; //最终需要转换的样子
//进行上下左右移动
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
queue<string> q; //q用来存放转换后的图
unordered_map<string,int> mp; //存放当前图 + 存放交换次数所得的当前图
string swap_s(int st,int ed,string s)
{
char c=s[st];
s[st]=s[ed];
s[ed]=c;
return s;
}
int bfs(string s)
{
q.push(s);
mp[s]=0; //目前是交换了0次
while(!q.empty())
{
string tmp=q.front();q.pop();
//这里必须先统计一下 不然后面会交换 影响步数最后的交换次数
int d=mp[tmp];
if(tmp==end_s)
{
return d;
}
int t=tmp.find('x'); //找到具体位置
int x=t/3; //得到x的坐标
int y=t%3; //得到y的坐标
//否则就开始执行
for(int i=0;i<4;i++)
{
int t1=x+dx[i],t2=y+dy[i];
if(t1>=0 && t1<3 && t2>=0 && t2<3)
{
//二维转一维坐标
int xy=t1*3+t2;
//进行交换
tmp=swap_s(xy,t,tmp);
unordered_map<string,int>:: iterator iter=mp.find(tmp);
if(iter==mp.end()) //是否能找到 找不到 返回0
{
mp[tmp]=d+1;
q.push(tmp);//读入
}
tmp=swap_s(xy,t,tmp); //还原 方便下一个地图移动
}
}
}
//不能走到指定的路线
return -1;
}
int main(void)
{
string s;
for(int i=0;i<3;i++)
{
for(int j=0;j<3;j++)
{
char c;cin >> c;
s+=c;
}
}
cout << bfs(s) << endl;
return 0;
}
unordered_map是$O(1)$,map是$O(log2{n})$
对 今天想的时候以为map能过 哈哈哈