如题,其中使用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;
}
大佬们能帮忙看一下怎么改进吗