自动机械装置（Robot）

合肥市第39届信息学竞赛（2022年）

题目描述 Description

小可可的学校引进了一台智能清洁机器人,学校将机器人的工作区域划分为一个 n x n 大小的网格。左上角单元格坐标为(0,0)。右下角单元格坐标为(n-1,n-1)。

智能清洁机器人可以接受4种移动指令:
‘L’(向左移动)，‘R’(向右移动)，‘U’(向上移动)和’D’(向下移动)。
收一条指令后，机器人会按指令方向移动一个单元格。小可可给机器人的指令序列是一个长度为 m 的字符串 c，其中仅包含’L’、‘R’、'U’和’D’四种字符。机器人可以从c中的第i条指令 ci(0≤i≤m-1)开始执行，它将会逐条指令连续执行，直到指令序列结束。
在遇到下述情况之一时，机器人将会停止移动:

1. ci的下一条指令将导致机器人移动到网格之外。
2. ci没有后续指令可以执行。
   机器人最开始位于坐标为(row,col)的单元格上。
   小可可想知道，若机器人从指令序列c中第i条指令d开始执行，可以连续执行的指令数目。

输入描述 Input Description

共3行，第一行两个正整数 n.m 分别表示网格的行列数、指令序列的长度。第二行包含两个正整数 row和col，表示机器人最开始位于坐标为(row,col)的单元格上。第三行是一个长度为m的字符串c，表示小可可给机器人的指令序列。

输出描述 Output Description

输出共m行，每行一个整数。第i行表示从c中第i条指令ci开始执行，机器人可以连续执行的指令数目。

样例输入 Sample Input

输入：（robot.in) 3 6 0 1 RRDDLU

样例输出 Sample Output

输出：(robot.out) 1 5 4 3 1 0

数据范围及提示 Data Size & Hint

样例解释：
机器人从(0,1)出发，并从第 ⅰ条指令开始执行:

i	机器人可以连续执行的指令数目
0	"RRDDLU"在移动到网格外之前，只能执行一条"R"指令。
1	"RDDLU"可以执行全部五条指令，机器人仍在网格内，最终到达(0,0)。
2	"DDLU"可以执行全部四条指令，机器人仍在网格内，最终到达(0,0)。
3	"DLU”可以执行全部三条指令，机器人仍在网格内，最终到达(0,0)。
4	"LU"在移动到网格外之前，只能执行一条"L"指令。
5	"U"如果向上移动，将会移动到网格外。

保证对于所有数据满足:1≤n≦60,1≤m≤2000。0≤row, col≤n-1\

本题用的是模拟算法：

代码：

#include<iostream>
using namespace std;
int n,m,row,col;
string s;

int main(){
	cin>>n>>m>>row>>col>>s;
	s=" "+s;
	for(int i=1;i<=m;i++){
		int x=row,y=col,cnt=0;
		for(int j=i;j<=m;j++){
			if(s[j]=='U') x--;
			if(s[j]=='D') x++;
			if(s[j]=='L') y--;
			if(s[j]=='R') y++;
			if(x<0||x>n-1||y<0||y>n-1) break;
			cnt++;
		}
		cout<<cnt<<endl;
	}
	return 0;
}