@[xiaozhangawa](/user/906102) 特判少了
如```120345678```
这样的s，你的程序会把```
123045678```当成一个合法的ns
by ENJOuYang @ 2024-03-11 18:27:39
@[ENJOuYang](/user/798144) 我再改改，谢谢 dalao
by xiaozhangawa @ 2024-03-16 15:43:48
```c++
我和你一样的做法，但是改完了之后还是有个点wa了
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
#include<string>
using namespace std;
string dest = "123804765";
map<string, bool>hashp;
queue<pair<string,int>>q;
string pos;
int cnt;
int dx[4] = { -3,3,-1,1 };//上下左右
bool rightgo(int p0, int go,int d)
{
if (go < 0 || go>8) return false;
if (p0 % 3 == 0 && d == -1) return false;//特判左边界
if (p0 % 3 == 2 && d == 1) return false;//特判右边界
return true;
}
int main()
{
cin >> pos;
q.push(make_pair(pos,0));//pos记录当前状态，cnt记录移动步数
hashp[pos] = true;//记录是否走过
while (!q.empty())
{
pos = q.front().first;
cnt = q.front().second;
int p0 = 0;
while (pos[p0] != '0') p0++;//0的位置
q.pop();
for (int i = 0; i < 4; i++)
{
int go = p0 + dx[i];
if (rightgo(p0,go,dx[i]))//移动坐标合法
{
char c = pos[go];
pos[go] = '0';
pos[p0] = c;
if (hashp[pos] != true)
{
hashp[pos] = true;
q.push(make_pair(pos,cnt+1));
if (pos == dest)
{
cout << cnt + 1;
return 0;
}
}
pos[go] = c;
pos[p0] = '0';
}
}
}
return 0;
}
by _Persever_ance @ 2024-04-26 21:59:45