求大佬改一改错,样例都过不了
查看原帖
求大佬改一改错,样例都过不了
278481
Link_Space楼主2020/8/8 16:00

找了很久实在没找出来错,求大佬指出错误

#include<iostream>
#include<map>
#include<queue>
using namespace std;
string sta;
struct node {
	string a;
	int x, y;
};
int dx[8] = { 1,-1,1,-1,2,-2,2,-2 };
int dy[8] = { -2,2,2,-2,1,-1,-1,1 };
string aim = "111110111100*110000100000";
void bfs(int x0,int y0)
{
	queue<node> qa, qb;
	map<string, int> ma, mb;
	qa.push({ sta,x0,y0 });
	qb.push({ aim,2,2 });
	while (!qa.empty() && !qb.empty())
	{
		if (qa.size() < qb.size())
		{
			node temp = qa.front();
			qa.pop();
			string s = temp.a;
			int x1 = temp.x;
			int y1 = temp.y;
			for (int i = 0; i < 8; i++)
			{
				int xx = x1 + dx[i];
				int yy = x1 + dy[i];
				if (xx < 0 || xx>=5 || yy < 0 || yy>=5)
					continue;
				string xy = s;
				swap(xy[x1 * 5 + y1], xy[xx * 5 + yy]);
				if (ma[xy])
					continue;
				if (mb[xy]||xy==aim)
				{
					if (ma[s] + mb[xy] + 1 > 15)
					{
						cout << -1<<endl;
						return;
					}
					cout << ma[s] + mb[xy]+1<<endl;
					return;
				}
				ma[xy] = ma[s] + 1;
				qa.push({ xy,xx,yy });
			}
		}
		else
		{
			node temp = qb.front();
			qb.pop();
			string s = temp.a;
			int x1 = temp.x;
			int y1 = temp.y;
			for (int i = 0; i < 8; i++)
			{
				int xx = x1 + dx[i];
				int yy = x1 + dy[i];
				if (xx < 0 || xx>=5 || yy < 0 || yy>=5)
					continue;
				string xy = s;
				swap(xy[x1 * 5 + y1], xy[xx* 5 + yy]);
				if (mb[xy])
					continue;
				if (ma[xy]||xy==sta)
				{
					if (mb[s] + ma[xy] + 1 > 15)
					{
						cout << -1<<endl;
						return;
					}
					cout << mb[s] + ma[xy] + 1<<endl;
					return;
				}
				mb[xy] = mb[s] + 1;
				qb.push({ xy,xx,yy });
			}
		}
	}
	cout << -1<<endl;
}
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		for (int i = 1; i <= 5; i++)
		{
			string x;
			cin >> x;
			sta += x;
		}
		for (int i = 0; i < sta.size(); i++)
		{
			if (sta[i] == '*')
			{
				bfs(i / 5, i % 5);
					break;
			}
		}
		sta = "";
	}
	return 0;
}
2020/8/8 16:00
加载中...