A*求助
  • 板块P5507 机关
  • 楼主Bodhi
  • 当前回复0
  • 已保存回复0
  • 发布时间2022/8/8 15:50
  • 上次更新2023/10/27 16:26:55
查看原帖
A*求助
364848
Bodhi楼主2022/8/8 15:50

如题,其中使用unordered_map判重的代码最后一个点TLE了(记录);但是没判重的时间能过,但是最后4个点都MLE(记录

//有判重的TLE
#include <bits/stdc++.h>
using namespace std;

struct Node
{
	string status; //两个代码的Node在这里不同,有判重的使用string,没有判重的使用int数组
	int guess = 0, step = 0, ans[18] = {0}; //题目给出了最大步数为17
	bool operator<(const Node &x) const
	{
		return step + guess > x.guess + x.step;
	}
};
inline int cnt(string status) //返回差值
{
	int res = 0, sz = status.size();
	for (register int j = 1; j < sz; ++j)
	{
		if (status[j] != '1')
		{
			++res;
		}
	}
	return res;
}
priority_queue<Node> q;
unordered_map<string, bool> m;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int a[13][5] = {0};
	char c;
	register int i, j;
	Node temp, next;
	temp.status += ' ';
	for (i = 1; i <= 12; ++i)
	{
		cin >> c;
		temp.status = temp.status + c;
		for (j = 1; j <= 4; ++j)
		{
			cin >> a[i][j];
		}
	}
	m[temp.status] = true;
	temp.step = 0;
	temp.guess = cnt(temp.status);
	q.push(temp);
	while (!q.empty())
	{
		temp = q.top();
		q.pop();
		if (!temp.guess)
		{
			cout << temp.step << "\n";
			for (j = 1; j <= temp.step; ++j)
			{
				cout << temp.ans[j] << ' ';
			}
			break;
		}
		for (j = 1; j <= 12; ++j)
		{ // x+1替换为x%4+1
			next = temp;
			next.status[a[j][next.status[j] ^ '0']] = ((next.status[a[j][next.status[j] ^ '0']] ^ '0') % 4 + 1) + '0';
			next.status[j] = ((next.status[j] ^ '0') % 4 + 1) + '0';
			if (!m[next.status]) //还没来过这个状态才进行下面的操作
			{
				m[next.status] = true;
				next.step = temp.step + 1;
				next.ans[next.step] = j;
				next.guess = cnt(next.status);
				q.push(next);
			}
		}
	}
	return 0;
}

//没有判重的MLE
#include <bits/stdc++.h>
using namespace std;

struct Node
{
	int status[13], guess, step, ans[20]; //题目说明中给出了最大步数为17
	bool operator<(const Node &x) const
	{
		return step + guess > x.guess + x.step;
	}
};
inline int cnt(int status[]) //返回差值
{
	int res = 0;
	for (register int j = 1; j <= 12; ++j)
	{
		if (status[j] != 1)
		{
			++res;
		}
	}
	return res;
}
int a[15][10];
priority_queue<Node> q;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	register int i, j;
	Node temp, next;
	for (i = 1; i <= 12; ++i)
	{
		cin >> temp.status[i];
		for (j = 1; j <= 4; ++j)
		{
			cin >> a[i][j];
		}
	}
	temp.step = 0;
	temp.guess = cnt(temp.status);
	q.push(temp);
	while (!q.empty())
	{
		temp = q.top();
		q.pop();
		if (!temp.guess)
		{
			cout << temp.step << "\n";
			for (j = 1; j <= temp.step; ++j)
			{
				cout << temp.ans[j] << ' ';
			}
			break;
		}
		for (j = 1; j <= 12; ++j)
		{ // x+1替换为x%4+1
			next = temp;
			next.status[a[j][next.status[j]]] = next.status[a[j][next.status[j]]] % 4 + 1;
			next.status[j] = next.status[j] % 4 + 1;
			next.step = temp.step + 1;
			next.ans[next.step] = j;
			next.guess = cnt(next.status);
			q.push(next);
		}
	}
	return 0;
}

大佬们能帮忙看一下怎么改进吗

2022/8/8 15:50
加载中...