牛客 小a与星际探索 bfs
链接：https://ac.nowcoder.com/acm/contest/317/C?&headNav=acm
来源：牛客网
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld
题目描述
小a正在玩一款星际探索游戏，小a需要驾驶着飞船从11号星球出发前往nn号星球。其中每个星球有一个能量指数pp。星球ii能到达星球jj当且仅当pi>pjpi>pj。
同时小a的飞船还有一个耐久度tt，初始时为11号点的能量指数，若小a前往星球jj，那么飞船的耐久度会变为t⊕pjt⊕pj(即tt异或pjpj，关于其定义请自行百度)
小a想知道到达nn号星球时耐久度最大为多少
同时小a的飞船还有一个耐久度tt，初始时为11号点的能量指数，若小a前往星球jj，那么飞船的耐久度会变为t⊕pjt⊕pj(即tt异或pjpj，关于其定义请自行百度)
小a想知道到达nn号星球时耐久度最大为多少
注意：对于每个位置来说，从它出发可以到达的位置仅与两者的p有关，与下标无关
输入描述:
第一行一个整数pi
输出描述:
一个整数表示到达−1
备注:
1⩽n,∀pi⩽3000
这个题目可以处理一下，也可以不处理，差不多。
这个bfs，需要用vis标记一下，这个vis标记，是去标记这个得到的数值。
这个是为了不超内存，让尽量少的数进入队列。
还要注意的就是这个题目的理解，应该是只要耐久度大于想去的星球才可以降落。
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <queue>
#define inf 0x3f3f3f3f
using namespace std;
const int maxn = 3e4;
int a[maxn], b[maxn],k, ans= -1;
bool vis[maxn];
int n;
struct node
{
int id, num;
node(int id = 0, int num = 0) :id(id), num(num) {}
};
void bfs()
{
queue<node>que;
que.push(node(1, b[1]));
vis[b[1]] = true;
while (!que.empty())
{
node u = que.front(); que.pop();
int x = u.id, y = u.num;
for (int i = 2; i < k; i++)
{
if (b[i] >= y) continue;
if(i==k-1)
{
ans = max(ans, y^b[i]);
continue;
}
if (vis[y^b[i]]) continue;
vis[y^b[i]] = true;
que.push(node(i, y^b[i]));
}
}
}
int main()
{
k = 1;
cin >> n;
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
if (a[1] <= a[n])
{
printf("-1
");
return 0;
}
for (int i = 1; i <= n; i++)
{
if (a[i] > a[1]) continue;
if (a[i] < a[n]) continue;
b[k++] = a[i];
}
bfs();
printf("%d
", ans);
return 0;
}