Codeforces 1607E

题意描述

给你一个\(n\times m\)的矩阵，机器人最初从\((1,1)\)开始行动，给你一个命令序列，机器人依次执行该命令序列，让你求一个坐标\((x,y)\)，使得机器人从这个坐标开始，能够尽可能多的执行命令序列。

思路

根据命令序列，可以维护一个机器人运动范围的矩阵，从而根据矩阵来得到答案。

AC代码

#include 

#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()

using namespace std;
using ll = long long;
using pii = std::pair;

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const double eps = 1e-10;

void solve()
{
    int n, m;
    cin >> n >> m;
    string s;
    cin >> s;
    int x = 0, y = 0, maxl = 0, maxr = 0, maxu = 0, maxd = 0;
    int ansx = 1, ansy = 1;
    for(int i = 0; i < sz(s); ++i)
    {
        if(s[i] == 'U') --x;
        else if(s[i] == 'R') ++y;
        else if(s[i] == 'L') --y;
        else if(s[i] == 'D') ++x;
        maxl = min(maxl, y);
        maxr = max(maxr, y);
        maxu = min(maxu, x);
        maxd = max(maxd, x);
        if(maxd - maxu + 1 > n)
        {
            if(x == maxu) maxu++;
            break;
        }
        if(maxr - maxl + 1 > m)
        {
            if(y == maxl) maxl++;
            break;
        }
    }
    cout << 1 - maxu << ' ' << 1 - maxl << '\n';

}


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout << std::fixed << std::setprecision(10);
    int _ = 1;
    cin >> _;
    while(_--) solve();
#ifdef dejavu
    cout << "The run time is:" << (double)clock() / CLOCKS_PER_SEC << "s" << '\n';
#endif
}