华为春招笔试打怪兽
优先队列，按照当前已经消灭的怪兽数量倒序排列，限制每个位置访问的次数防止循环
#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
int cmp(int a, int b)
{
return a > b;
}
struct Node {
int x, y, step, cnt;//位置x,y，当前步数，当前消灭的怪兽个数
bool operator<(const Node& a) const
{
if(cnt != a.cnt)
return cnt < a.cnt;
return step > a.step;
}
};
int main()
{
int n, cnt = 0;
vector<int>tmp, notUsed;//notused记录当前没有消灭的怪兽的等级
while (cin >> n)
{
//if (n == -1)break;
if (n >= 2)
notUsed.push_back(n);
tmp.push_back(n);
}
cnt = (int)sqrt(tmp.size());
sort(notUsed.begin(), notUsed.end(), cmp);
int maxCnt = notUsed.size();
if (maxCnt == 0)
{
cout << "0" << endl;
return 0;
}
vector<vector<int>>v(cnt, vector<int>(cnt)), flag(cnt, vector<int>(cnt, 0));
int k = 0;
for (int i = 0; i < cnt; i++)
{
for (int j = 0; j < cnt; j++)
{
v[i][j] = tmp[k++];
}
}
priority_queue<Node>pq;
if (v[0][0] == notUsed.back())//初始位置是等级最低的怪兽
{
pq.push({ 0,0,0,1 });
//flag[0][0] = 1;
v[0][0] = 0;
notUsed.pop_back();
}
else if (v[0][0] > notUsed.back() || v[0][0] == 0)//高等级怪兽或者陷阱
{
cout << "-1" << endl;
return 0;
}
else//陆地
{
pq.push({ 0,0,0,0 });
}
int dir[4][2] = { 1,0,0,1,-1,0,0,-1 };
while (!pq.empty())
{
Node a = pq.top();
pq.pop();
flag[a.x][a.y]++;//更新当前位置访问的次数
if (notUsed.size() == 0)//怪兽消灭完
{
cout << a.step << endl;
return 0;
}
if (flag[a.x][a.y] > maxCnt)//经过某位置超过一定次数，则产生循环
{
cout << "-1" << endl;
return 0;
}
for (int i = 0; i < 4; i++)
{
int dx = a.x + dir[i][0];
int dy = a.y + dir[i][1];
if (dx >= 0 && dx < cnt && dy >= 0 && dy < cnt)
{
if (v[dx][dy] == 1)
{
pq.push({ dx, dy, a.step + 1, a.cnt });
}
else if (v[dx][dy] == notUsed.back())
{
v[dx][dy] = 1;
pq.push({ dx, dy, a.step + 1, a.cnt+1 });
notUsed.pop_back();
}
}
}
}
cout<<"-1"<<endl;
return 0;
} 