CF359E.Neatness

提高+/省选-

通过率:0%

时间限制:2.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Simon loves neatness. So before he goes to bed, Simon wants to complete all chores in the house.

Simon's house looks like a rectangular table consisting of n rows and n columns from above. All rows of the table are numbered from 1 to n from top to bottom. All columns of the table are numbered from 1 to n from left to right. Each cell of the table is a room. Pair (x, y) denotes the room, located at the intersection of the x-th row and the y-th column. For each room we know if the light is on or not there.

Initially Simon is in room (_x_0, _y_0). He wants to turn off the lights in all the rooms in the house, and then return to room (_x_0, _y_0). Suppose that at the current moment Simon is in the room (x, y). To reach the desired result, he can perform the following steps:

  1. The format of the action is "1". The action is to turn on the light in room (x, y). Simon cannot do it if the room already has light on.
  2. The format of the action is "2". The action is to turn off the light in room (x, y). Simon cannot do it if the room already has light off.
  3. The format of the action is "dir" (dir is a character). The action is to move to a side-adjacent room in direction dir. The direction can be left, right, up or down (the corresponding dir is L, R, U or D). Additionally, Simon can move only if he see a light in the direction dir. More formally, if we represent the room, Simon wants to go, as (nx, ny), there shold be an integer k (k > 0), that room (x + (nx - x)k, y + (ny - y)k) has a light. Of course, Simon cannot move out of his house.

Help Simon, find the sequence of actions that lets him achieve the desired result.

西蒙喜欢整洁。因此,他睡觉前希望完成家里的所有家务。

从上方看,西蒙的家是一个由 nn 行 nn 列构成的矩形表格。表格的所有行从上到下依次编号为 11 到 nn;所有列从左到右依次编号为 11 到 nn。表格中的每个单元格代表一个房间。二元组 (x, y)(x,\,y) 表示位于第 xx 行与第 yy 列交点处的房间。对于每个房间,我们已知其中的灯是开着还是关着。

初始时,西蒙位于房间 (x0, y0)(x_0,\,y_0)。他希望关闭家中所有房间的灯,然后返回房间 (x0, y0)(x_0,\,y_0)。假设当前西蒙位于房间 (x, y)(x,\,y),为达成目标,他可执行以下操作:

  1. 操作格式为 "1":表示打开房间 (x, y)(x,\,y) 的灯。若该房间灯已开启,则西蒙不能执行此操作。
  2. 操作格式为 "2":表示关闭房间 (x, y)(x,\,y) 的灯。若该房间灯已关闭,则西蒙不能执行此操作。
  3. 操作格式为 "dir"(其中 dir 是一个字符):表示朝方向 dir 移动至一个相邻的房间。方向可以是左、右、上或下(对应字符分别为 L、R、U 或 D)。此外,西蒙仅当在方向 dir 上能看到灯光时才能移动。更准确地说,若西蒙想要前往的房间记为 (nx, ny)(nx,\,ny),则需存在某个正整数 k (k>0)k\,(k > 0),使得房间 (x+(nx−x)⋅k, y+(ny−y)⋅k)(x + (nx - x) \cdot k,\, y + (ny - y) \cdot k) 中有灯亮着。当然,西蒙不能移出房屋边界。

请帮助西蒙找出一串操作序列,使其能达成上述目标。

输入格式

The first line contains three positive integers n, _x_0, _y_0 (2 ≤ n ≤ 500, 1 ≤ _x_0, _y_0 ≤ n).

Next n lines contain the description of rooms in the house. The i-th line contains n space-separated integers _a__i_1, _a__i_2, ..., a__in. If number a__ij equals zero, then room (i, j) has light off, and if number a__ij equals one, then room (i, j) has light on. It is guaranteed that at least one room has light on.

第一行包含三个正整数 nn、x0x_0、y0y_0(满足 2≤n≤5002 \leq n \leq 500,1≤x0,y0≤n1 \leq x_0, y_0 \leq n)。

接下来的 nn 行描述了房屋中各房间的状态。第 ii 行包含 nn 个用空格分隔的整数 ai1, ai2, …, aina_{i1},\,a_{i2},\,\dots,\,a_{in}。若 aij=0a_{ij} = 0,则房间 (i, j)(i,\,j) 的灯处于关闭状态;若 aij=1a_{ij} = 1,则房间 (i, j)(i,\,j) 的灯处于开启状态。保证至少有一个房间的灯是开启的。

输出格式

If there is no desired sequence of actions, print "NO" (without the quotes). Otherwise, print "YES" (without the quotes) and the description of the required sequence of actions as a string. Note that you do not have to minimize the length of the sequence of actions but you shouldn't use more than 3·106 actions.

如果不存在满足要求的操作序列,则输出 "NO"(不带引号)。否则,输出 "YES"(不带引号),并输出所需操作序列的描述(以字符串形式)。注意:你无需最小化操作序列的长度,但操作总数不得超过 3⋅1063 \cdot 10^6 次。

输入输出样例

  • 输入#1

    3 1 1
    1 0 0
    0 1 0
    1 0 0

    输出#1

    YES
    D1R2L2D2UU2
  • 输入#2

    3 1 1
    1 0 0
    0 1 0
    0 0 1

    输出#2

    NO

输入解题思路,AI测评打分。不知道怎么写?

首页