题意:
找出能够满足给定字符串移动的最长的指令的位置
思路:
刚开始我想如果每个点都模拟肯定超时,所以我想去先以一个固定的点来执行这些指令,然后将他放到原图中,算清楚这其中的偏移量即可,然后我实现起来有点复杂,是去变动他的左右区间来求这个范围的,然后就会有很多小的bug, 后来一想,我只要按照他给定的字符串模拟,取出4个边界,然后在取的过程中判断是否超出了n, m边界,如果超出了,就相当于不管取哪个位置都是死的,直接结束,我是以0, 0,作为原点的,最后的偏移量就是1 + abs(minx), 1 + abs(miny), 就相当于把以(0,0)所得出的矩阵范围放入n, m的网格中,求出(0, 0)对应的坐标值
总结:
取出位置来模拟出范围,然后对应偏移量求解即可
点击查看代码
#include <bits/stdc++.h>
#define endl '\n'
#define IOS ios::sync_with_stdio(false);
using namespace std;
typedef long long ll;
int T, n, m;
string s;
int main()
{
IOS; cin.tie(0), cout.tie(0);
cin >> T;
while (T--)
{
cin >> n >> m;
cin >> s;
int x = 0, y = 0;
int minx = 0, maxx = 0, miny = 0, maxy = 0;
int ansx = 1, ansy = 1;
for (auto c : s)
{
if (c == 'L')
miny = min(miny, --y);
else if (c == 'R')
maxy = max(maxy, ++y);
else if (c == 'U')
minx = min(minx, --x);
else if (c == 'D')
maxx = max(maxx, ++x);
if (maxx - minx >= n || maxy - miny >= m)
break;
ansx = 1 + abs(minx);
ansy = 1 + abs(miny);
}
cout << ansx << " " << ansy << endl;
}
return 0;
}