Public Judge

pjudge

Time Limit: 1 s Memory Limit: 512 MB Total points: 100

# 21791. 【NOIP Round #6】探索

统计

题目描述

你有一个机器人在无限大的平面上走,初始位置为 $(0,0)$ 。

你向它发送了若干个指令,每个指令是 LRUD 之一。如果机器人原来的位置是 $(x,y)$ ,那么四条指令分别会使其移动到 $(x-1,y),(x+1,y),(x,y+1),(x,y-1)$ 。

平面上可能有若干个障碍,但你不知道它们的具体位置。当机器人尝试移动时,它会先判断目标位置是否有障碍,如果存在障碍就会忽略这条指令。

给定长度为 $n$ 的指令序列,求出机器人在执行完这 $n$ 条指令之后可能会在哪些位置。

输入格式

第一行一个正整数 $n$ 。

第二行一个长度为 $n$ 的字符串,由 LURD 组成,表示操作序列。

输出格式

第一行一个正整数 $k$ ,表示可能的位置个数。

接下来 $k$ 行,每行两个整数 $x_i,y_i$ ,表示一个可能的位置。你需要把所有位置以 $x$ 为第一关键字、$y$ 为第二关键字从小到大排序后输出。

样例

样例输入 1

2
RU

样例输出 1

4
0 0
0 1
1 0
1 1

样例解释 1

一组可能的状态是在 $(1,0)$ 有障碍而 $(0,1)$ 没有,那么机器人会忽略第一条指令,然后执行第二条指令,来到 $(0,1)$ 。

样例输入 2

4
LRUD

样例输出 2

4
0 -1
0 0
1 -1
1 0

数据范围

对于 $20\%$ 的数据,保证 $1\le n\le 2$ 。

对于 $40\%$ 的数据,保证 $1\le n\le 4$ 。

对于所有数据,保证 $1\le n\le 20$ 。