看了个双向bfs的例题,做了之后却不知道哪里错了QWQ
求助a
#include<bits/stdc++.h>
using namespace std;
int d[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int ans = 123804765;
inline int toget(int map2[3][3])
{
int sum = 0, bs = 1;
for(int i = 2;i >= 0; --i)
for(int j = 2;j >= 0; --j)
{
sum += bs * map2[i][j];
bs *= 10;
}
return sum;
}
queue<int> q1, q2;
map<int, int> cc;//是前搜,2是后搜
map<int, int> res;//只是不知道要开多大数组而已= - =
int main()
{
int mapp[3][3];
int g; cin >> g;
if(ans == g) return !puts("0");//压行
q1.push(g); cc[g] = 1; res[g] = 0;
q2.push(ans); cc[ans] = 2; res[ans] = 0;
bool is;
while(!q1.empty() or !q2.empty())
{
int now, x, y;
if (q1.size() < q2.size() || (q1.size() > q2.size() && q2.empty()))
{
now = q1.front(); q1.pop(); is = true;
}
else
{
now = q2.front(); q2.pop(); is = false;
}
for(int i = 2, k = now; i>= 0; --i)
for(int j = 2;j >= 0; --j)
{
mapp[i][j] = k % 10;
k /= 10;
if(mapp[i][j] == 0)
x = i, y = j;//
}
for(int k = 0;k < 4; ++k)
{
int _x = x + d[k][0], _y = y + d[k][1];
if(_x >= 0 and x < 3 and _y >= 0 and _y < 3)
{
swap(mapp[x][y], mapp[_x][_y]);
int temp = toget(mapp);
if(cc[temp] = cc[now])
{
swap(mapp[x][y], mapp[_x][_y]);
continue;
}
if(cc[now] + cc[temp] == 3)
{
cout << res[now] + 1 + res[temp];
return 0;
}
res[temp] = res[now] + 1;
cc[temp] = cc[now];
if(is) q1.push(temp);
else q2.push(temp);
swap(mapp[x][y], mapp[_x][_y]);//就是dfs回溯
}
}
}
return 0;
}