双向bfsの懵
查看原帖
双向bfsの懵
307483
苏黎世楼主2021/1/8 19:01

看了个双向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;
} 
2021/1/8 19:01
加载中...