# Gym 101981K - Kangaroo Puzzle - [玄学][2018-2019 ACM-ICPC Asia Nanjing Regional Contest Problem K]

2018/11/18 20:58

Your friend has made a computer video game called “Kangaroo Puzzle” and wants you to give it a try

for him. As the name of this game indicates, there are some (at least 2) kangaroos stranded in a puzzle

and the player’s goal is to control them to gather. As long as all the kangaroos in the puzzle get together,

they can escape the puzzle by the miraculous power of kangaroos.

The puzzle is a n × m grid consisting of nm cells. There are walls in some cells and the kangaroos cannot

enter these cells. The other cells are empty. The kangaroos can move in the following direction: up, down,

left and right. It is guaranteed that one kangaroo can move from an empty cell to any other. It is also

guaranteed that there is no cycle in the puzzle — that is, it’s impossible that one kangaroo can move from

an empty cell, pass by several distinct empty cells, and then back to the original cell.

There is exactly one kangaroo in every empty cell at the beginning. You can control the kangaroos by

pressing the button U, D, L, R on your keyboard. The kangaroos will move simultaneously according to the

button you press. For instance, if you press the button U, a kangaroo would move to the upper cell if it

exists and is empty; otherwise, the kangaroo will stay still. You can press the buttons for at most 50000

times. If there are still two kangaroos standing in different cells after 50000 steps, you will lose the game.

Input

The first line contains two integers, n and m (1 ≤ n, m ≤ 20), the height and the width of the puzzle,

respectively. Each of the next n lines contains a (0,1)-string of length m, representing the puzzle. If the

j-th character of the i+1-th line is 1, then the cell at the i-th row and the j-th column is empty; otherwise

(i.e. it is 0), the corresponding cell is blocked and cannot be entered.

Output

Print a string consisting of U, D, L, R, such that all kangaroos will get together after pressing the buttons

in the order of this string. The length of the string should not exceed 50000. There are many possible

valid answers, so just print any of them.

Examples

standard input

4 4

1111

1001

1001

1110

standard output

LLUUURRRDD

standard input

2 15

111111111111111

101010101010101

standard output

ULLLLLLLLLLLLLL

AC代码：

#include<bits/stdc++.h>
using namespace std;
int n,m;
char tmp[23],d[4]={'L','R','U','D'};
int main()
{
srand(6510561);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%s",tmp);
for(int i=1;i<=50000;i++) printf("%c",d[rand()%4]);
}

0
0 收藏

0 评论
0 收藏
0