题目链接
题解
模拟题。
观察题目，我们发现，无论问的是前/后/左/右，你都只会在一条直线上走，那对于这条直线，我们可以记录所有这条直线上的障碍物，然后找到距离当前点最近的障碍物，也就是说我们只能走到那个障碍物那块。
虽然数据范围高达 \(10^9\)，但是 \(n\le10^5\)，所以用 \(map\) 套 \(set\) 就能轻松解决这一问题。
注意：我们不能把 \(h+w\) 的行和列进行初始化，只能用到哪一列，哪一列初始化。
代码
#include <iostream>
#include <set>
#include <map>
#include <algorithm>
using namespace std;
int n,m,sx,sy,wall_cnt,q;
map <int,set <int> > row,col;
int main () {
cin >> n >> m >> sx >> sy >> wall_cnt;
// for (int i = 1;i <= n;i++) row[i].insert (0);
// for (int i = 1;i <= m;i++) col[i].insert (0);
// for (int i = 1;i <= n;i++) row[i].insert (m + 1);
// for (int i = 1;i <= m;i++) col[i].insert (n + 1);
for (int i = 1;i <= wall_cnt;i++) {
int x,y;
scanf ("%d%d",&x,&y);
row[x].insert (y),col[y].insert (x);
}
scanf ("%d",&q);
while (q--) {
char dir[2];
int x;
scanf ("%s%d",dir,&x);
row[sx].insert (0),row[sx].insert (m + 1);
col[sy].insert (0),col[sy].insert (n + 1);
if (*dir == 'L' || *dir == 'R') {
auto lt = row[sx].lower_bound (sy),ut = row[sx].upper_bound (sy);
if (*dir == 'L') sy = max (*(--lt) + 1,sy - x);
else sy = min (*ut - 1,sy + x);
}
else {
auto lt = col[sy].lower_bound (sx),ut = col[sy].upper_bound (sx);
if (*dir == 'U') sx = max (*(--lt) + 1,sx - x);
else sx = min (*ut - 1,sx + x);
}
printf ("%d %d\n",sx,sy);
// puts ("-----------");
}
return 0;
}