25分暴力代码：
储存为邻接矩阵 进行广度遍历 寻找到最近的距离和结点
然后去进行坐标变换操作
问题就是：邻接矩阵太大了存不下 而且只需要判断当前坐标是否满足条件 不需要都遍历 ，理论上维护坐标位置 每次根据数学表达式决定是否更新就可以。
#include <bits/stdc++.h>
using namespace std;
int n, m, p, q;
vector<vector<int>> graph(1003, vector<int>(1003, 0));
int dx[8] = {1,1,0,-1,-1,-1,0,1};
int dy[8] = { 0,1,1,1,0,-1,-1,-1 };
map<int, pair<int, int>> worker;
struct node {
pair<int, int> p;
int di;
node() {}
node(int u, int v, int k, int di) { p.first = u; p.second = v; k = k; di = di; }
};
//获得V1集合和对应的坐标
pair <map<int, vector<node>>, set<int>> get_V1(int u, int v) {
map<int, vector<node>> V1_map;
set<int> V1_set;
//遍历整张图 从阴阳龙结点开始八个方向为一个循环 循环次数是个问题
int count = max(max(m - v, v - 1),max(u - 1, n - u));
//循环count次 count代表距离
for (int i = 1; i <= count; i++) {
//寻找八个方向的员工
for (int j = 0; j < 8; j++) {
int now_x = u + dx[j];
int now_y = v + dy[j];
if (graph[now_x][now_y] == 1) {
V1_map[i].push_back(node(u,v,i,j));
V1_set.insert(i);
}
}
}
return { V1_map,V1_set };
}
//改变位置
void change(vector<node> nearest, int t,int k) {
for (node worker : nearest) {
int now_x = worker.p.first;
int now_y = worker.p.second;
int di = worker.di;
int k = k;
int new_x = now_x + k * dx[(di + t) % 8];
int new_y = now_y + k * dy[(di + t) % 8];
graph[now_x][now_y] = 0;
graph[new_x][new_y] = 1;
}
}
//work函数
void work(int u, int v, int t) {
pair<map<int, vector<node>>,set<int>> V1=get_V1(u,v);
if (V1.second.empty())
return;
else {
int k = V1.first.begin()->first;
vector<node> nearest=V1.first[k];
change(nearest, t,k);
}
}
//获得坐标结果
int get_result() {
int result;
for (int i = 1; i <= p; i++) {
if (i == 1)
result = i * worker[i].first + worker[i].second;
else
result = result ^ (i * worker[i].first + worker[i].second);
}
return result;
}
int main() {
// n*m:代表图的大小 （1，1） （n,m）
// p:员工个数 1-p
// q：阴阳龙现身次数
cin >> n >> m >> p >> q;
for (int i = 1; i <= p; i++) {
int x, y;
cin >> x >> y;
graph[x][y] = 1;
worker[i] = { x,y };
}
while (q--) {
int u, v, t;
cin >> u >> v >> t;// 阴阳龙坐标：(u,v) 强度：t
work(u, v, t);
cout << get_result();
}
}
满分代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m, p, q;
cin >> n >> m >> p >> q;
vector<array<int, 2>> pos(p);
unordered_map<int, set<array<int, 2>>> row, col, ld, rd;
auto insert = [&](int id){
int x = pos[id][0], y = pos[id][1];
row[x].insert({y, id});
col[y].insert({x, id});
ld[x + y].insert({y, id});
rd[x - y].insert({y, id});
};
auto remove = [&](int id){
int x = pos[id][0], y = pos[id][1];
row[x].erase({y, id});
col[y].erase({x, id});
ld[x + y].erase({y, id});
rd[x - y].erase({y, id});
};
for(int i = 0; i < p; ++ i){
cin >> pos[i][0] >> pos[i][1];
insert(i);
}
for(int i = 0; i < q; ++ i){
int u, v, t;
cin >> u >> v >> t;
vector<array<int, 3>> candidate;
auto search = [&](const set<array<int, 2>>& people, int d, int dirr, int dirl){
auto pos = people.lower_bound(array<int, 2>{d, p});
if (pos != people.end()){
candidate.push_back({(*pos)[0] - d, (*pos)[1], dirr});
}
if (pos != people.begin()){
pos = prev(pos);
if ((*pos)[0] == d && pos != people.begin())
pos = prev(pos);
if ((*pos)[0] != d){
candidate.push_back({d - (*pos)[0], (*pos)[1], dirl});
}
}
};
search(row[u], v, 2, 6);
search(col[v], u, 0, 4);
search(ld[u + v], v, 3, 7);
search(rd[u - v], v, 1, 5);
if (candidate.empty())
continue;
sort(candidate.begin(), candidate.end(), [&](const array<int, 3>& a, const array<int, 3>& b){
return a[0] < b[0];
});
int mindis = min({u - 1, n - u, v - 1, m - v});
if (candidate[0][0] > mindis)
continue;
mindis = candidate[0][0];
for(int i = 0; i < candidate.size(); ++ i){
if (candidate[i][0] != mindis)
break;
int dis = candidate[i][0];
int id = candidate[i][1];
remove(id);
int dir = (candidate[i][2] + t) % 8;
pos[id][0] = u + dis * dx[dir];
pos[id][1] = v + dis * dy[dir];
insert(id);
}
}
LL ans = 0;
for(int i = 0; i < p; ++ i){
ans ^= (1ll * (i + 1) * pos[i][0] + pos[i][1]);
}
cout << ans << '\n';
return 0;
}