题目描述

班尼刚买了一台新的可编程机器人。

为了测试他的编码技能，他将机器人放置在了一个R行（从北到南编号为1到R）C列（从西到东编号为1到C）的矩形网格中，其中位于第r行第c列的方格的坐标表示为(r, c)。

最初,机器人位于方格(S_R,S_C)处。

班尼将给机器人下达N条指令,每条指令是N，S，E，W中的一条，分别指示机器人向北，向南，向东或向西移动一个方格。

如果机器人移动到之前到过的方格，则机器人将继续沿同一方向移动，直到它到达之前未曾进入过的方格为止。

班尼永远都不会给机器人下达使其移出网格范围的指令。

现在请你帮助班尼计算一下，N次指令过后，他的机器人位于哪个方格内？

输入格式

第一行包含整数T，表示共有T组测试数据。

每组数据第一行包含5个整数N,R,C,S_R,S_C。

第二行包含一个N个字符的字符串表示N条指令，字符串中的字符一定是N，S，E，W中的一种。

输出格式

每组数据输出一个结果，每个结果占一行。

结果表示为“Case #x: r c”，其中x是组别编号（从1开始），(r, c)为最终所在位置的方格坐标。

数据范围

$ 1≤T≤10 $,
$ 1≤R,C,N≤5∗10^4 $,
$ 1≤S_R≤R $,
$ 1≤S_C≤C $,

样例

输入样例：

3
5 3 6 2 3
EEWNS
4 3 3 1 1
SESE
11 5 8 3 4
NEESSWWNESE

输出样例：

Case #1: 3 2
Case #2: 3 3
Case #3: 3 7

算法1

(模拟) $O(nlogn)$

• 定义两个函数，区间插入函数insert(),和移动函数move()。
• insert()函数会将移动点放入，二分找出出左右相邻区间,看左右是否相连来更新区间
• move函数则将会先二分找出出左右相邻区间，看当前要移动到的点会不会与其相连
• 模拟每段操作，先move再insert
• 考虑到左右区间的操作，可采用set + pair方式进行存储，利用set内置二分(lower_bound)函数进行二分

时间复杂度

一层循环$O(n)$
二分复杂度$O(logn)$
总时间复杂度$O(nlogn)$

参考文献

Google Kickstart

C++ 代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<set>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;

const int N = 5e4 + 10, INF = 1e9;
int n, r, c, f_x, f_y;
char ops[N];
set<PII> row[N], col[N];

//该函数实现每次向各个方向延伸，且检测是否要跳过相邻区间
//f_x代表每次位置，d代表方向
int move(set<PII>& segs, int f_x, int d)
{
    auto index = segs.lower_bound({f_x, f_x});//二分查找出比当前区间大且最近的区间
    if(d < 0){
        index --;
        if(index->y == f_x - 1) return index->x - 1;
        return f_x - 1;
    }
    if(d > 0){
        if(index->x == f_x + 1) return index->y + 1;
        return f_x + 1;
    }
    return -1;
}
//该函数实现将当前位置插入哪些区间
void insert(set<PII>& segs, int f_x)
{
    auto index = segs.lower_bound({f_x, f_x});
    //j即是比当前区间大且最近的区间，而index--操作使其便为比当前区间小且最近区间
    auto j = index--; 

    bool left = index->y == f_x - 1;
    bool right = j->x == f_x + 1;

    if(left && right){
        segs.insert({index->x, j->y});
        segs.erase(index);
        segs.erase(j);
    }
    else if(left){
        segs.insert({index->x, f_x});
        segs.erase(index);
    }else if(right){
        segs.insert({f_x, j->y});
        segs.erase(j);
    }else{
        segs.insert({f_x, f_x});
    }
}

int main()
{
    int T;
    int cnt = 1;
    cin >> T;
    while(T --){

        cin >> n >> r >> c >> f_x >> f_y;
        cin >> ops;

        for(int i = 0; i <= r; i++){
            row[i].clear();
            row[i].insert({-INF, -INF});
            row[i].insert({INF, INF});
        }
        for(int i = 0; i <= c; i++){
            col[i].clear();
            col[i].insert({-INF, -INF});
            col[i].insert({INF, INF});
        }
        for(int i = 0; i < n; i++){
            char op = ops[i];
            int dx, dy;
            if(op == 'N'){
                dy = f_y;
                dx = move(col[f_y], f_x, -1);
            }
            else if(op == 'S'){
                dy = f_y;
                dx = move(col[f_y], f_x, 1);
            }
            else if(op == 'E'){
                dx = f_x;
                dy = move(row[f_x], f_y, 1);
            }else{
                dx = f_x;
                dy = move(row[f_x], f_y, -1);
            }
            //cout << dx << " " << dy << endl;
            insert(row[f_x], f_y);
            insert(col[f_y], f_x);
            f_x = dx, f_y = dy;
        }
        printf("Case #%d: %d %d\n", cnt++, f_x, f_y);
    }
    return 0;
}