题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<algorithm>
#include<set>

using namespace std;

typedef pair<int, int>PII;

const int N = 50010, INF = 1e9;

int n, R, C;
char ops[N];

set<PII> row[N], col[N];

int move(set<PII>& segs, int x, int dir)
{
    auto i = segs.lower_bound({x, x});

    if (dir < 0)
    {
        i --;
        if (i->second == x - 1) return i->first - 1;
        return x  - 1;
    }
    if (dir > 0)
    {
        if (i->first == x + 1) return i->second + 1;
        return x  + 1;
    }
    return -1;
}

void insert(set<PII>& segs, int x)
{
    auto i = segs.lower_bound({x, x});
    auto j = i --;

    bool left = i->second == x - 1;
    bool right = j->first == x + 1;

    if (left && right)
    {
        segs.insert({i->first, j->second});
        segs.erase(i);
        segs.erase(j);
    }
    else if (left)
    {
        segs.insert({i->first, x});
        segs.erase(i);
    }
    else if (right)
    {
        segs.insert({x, j->second});
        segs.erase(j);
    }
    else
    {
        segs.insert({x, x});
    }

}

int main()
{
    int T;
    cin >> T;
    for (int cases = 1; cases <= T; cases ++)
    {
        int x, y;
        cin >> n >> R >> C >> x >> 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 c = ops[i];
            int dx, dy;
            if (c == 'N')
            {
                dy = y;
                dx = move(col[y], x, -1);
            }
            else if (c == 'S')
            {
                dy = y;
                dx = move(col[y], x, 1);
            }
            else if (c == 'W')
            {
                dx = x;
                dy = move(row[x], y, -1);
            }
            else
            {
                dx = x;
                dy = move(row[x], y, 1);
            }
            insert(row[x], y);
            insert(col[y], x);
            x = dx, y = dy;
        }
        printf("Case #%d: %d %d\n", cases, x, y);
    }
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla