2018icpc南京 Problem K. Kangaroo Puzzle

题意
每次可以把所有袋鼠整体往一个方向移动一步（不能走出边界和不能走到墙），为在不超过5e4步的情况下能否把全部袋鼠聚集在同一个位置

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

题意
每次可以把所有袋鼠整体往一个方向移动一步（不能走出边界和不能走到墙），为在不超过5e4步的情况下能否把全部袋鼠聚集在同一个位置

思路
数据范围 20*20，400个点，随便跑一个长度40000左右的字符串即可，总能汇合。
我写的比较烦，写了个dfs

#include <bits/stdc++.h>
typedef long long ll;
const ll mod = 1e9+7;
namespace fastIO {
    inline void input(int& res) {
        char c = getchar();res = 0;int f = 1;
        while (!isdigit(c)) { f ^= c == '-'; c = getchar(); }
        while (isdigit(c)) { res = (res << 3) + (res << 1) + (c ^ 48);c = getchar(); }
        res = f ? res : -res;
    }
    inline ll qpow(ll a, ll b) {
        ll ans = 1, base = a;
        while (b) {
            if (b & 1) ans = ans * base % mod;
            base = base * base % mod;
            b >>= 1;
        }
        return ans % mod;
    }
}
using namespace std;
using namespace fastIO;
const int N = 1e6+5;
int Case,n,m,sx,sy;
char mp[25][25];
string a;
int dir[4][2]={{0,1},{0,-1},{-1,0},{1,0}};
void dfs(int x,int y,int step){
	int nx,ny,t;
	if(step>30000) return;
	bool flag=true;
	while(flag){
		t=(rand()%4);
		nx=x+dir[t][0];
		ny=y+dir[t][1];
		if(nx>=0&&ny>=0&&nx<n&&ny<m) flag=false;
	}
	if(t==0) a+="U";
	else if(t==1) a+="D";
	else if(t==2) a+="L";
	else a+="R";
	dfs(nx,ny,step+1);
}
int main(){
	input(n),input(m);
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			scanf("%c",&mp[i][j]);
			if(mp[i][j]=='1') 
				sx=i,sy=j;
		}
	}
	dfs(sx,sy,0); 
	for(int i=0;i<20;i++) cout<<"U";
	for(int i=0;i<20;i++) cout<<"L";
	for(int i=0;i<20;i++) cout<<"R";
	for(int i=0;i<20;i++) cout<<"D";
	cout<<a;
	return 0;
}