#if !__INCLUDE_LEVEL__ #include __FILE__ const char DIR[4] = {'D', 'R', 'L', 'U'}; void output(vector &ans){ for( char c : ans){ cout << c; } cout << endl; } vector> seen; map> dir2num; ll h,w,p; struct A{ int cost; vector ans; int curX; int curY; bool operator<( const A& right ) const { return cost == right.cost ? ans.size() < right.ans.size() : cost < right.cost; } bool operator>( const A& right ) const { return cost == right.cost ? ans.size() > right.ans.size() : cost > right.cost; } }; int CalcCost(int X, int Y, vector &ans){ return (abs(19-X)+abs(19-Y))*100; } priority_queue, greater> que; void Astar(){ que.push(A{10000000, {'D','D'}, 0,0}); que.push(A{10000000, {'R','R'}, 0,0}); que.push(A{10000000, {'D','R'}, 0,0}); que.push(A{10000000, {'R','D'}, 0,0}); while (!que.empty()) { A a = que.top(); que.pop(); if (a.ans.size() > 400) { return; } ///////////////////////////////////////// ll score = 0; int cnt = 0; do{ output(a.ans); cin >> score; if (score == -1) { exit(0); } cnt++; if(cnt > 400)break; }while(score < a.ans.size()-2); if (score == a.ans.size() - 1) { a.ans.pop_back(); } else if (score == a.ans.size() - 2) { continue; } ///////////////////////////////////////// char skip_dir; if(a.ans.size() > 0){ switch ( a.ans.back()) { case 'L' : skip_dir='R'; break; case 'U' : skip_dir='D'; break; case 'R' : skip_dir='L'; break; case 'D' : skip_dir='U'; break; } } else{ skip_dir=' '; } for (int i = 0; i < 1; i++){ for (char dir : DIR ){ if (dir == skip_dir ){ continue; } int nxtX = dir2num[dir].first+a.curX; int nxtY = dir2num[dir].second+a.curY; if(nxtX < 0 || h <= nxtX || nxtY < 0 || w <= nxtY ){ // cerr << "ans1" << "\n"; continue; } if(seen[nxtX][nxtY] <= a.ans.size()+1){ // cerr << "ans2" << "\n"; continue; } seen[nxtX][nxtY] = a.ans.size()+1; vector ans2(a.ans); ans2.push_back(dir); // int cost = CalcCost(nxtX, nxtY, ans2); // que.push(A{cost, ans2, nxtX, nxtY}); for (char dir2 : DIR ){ int nxtX2 = dir2num[dir2].first+nxtX; int nxtY2 = dir2num[dir2].second+nxtY; if(nxtX2 < 0 || h <= nxtX2 || nxtY2 < 0 || w <= nxtY2 ){ // cerr << "ans1" << "\n"; continue; } if(seen[nxtX2][nxtY2] <= a.ans.size()+1){ // cerr << "ans2" << "\n"; continue; } vector ans3(ans2); ans3.push_back(dir2); int cost = CalcCost(nxtX2, nxtY2, ans3); que.push(A{cost, ans3, nxtX2, nxtY2}); } } } } } signed main() { cin >> h >> w >> p; vector> is_wall(h-1, vector(w-1)); seen.resize(h, vector(w, 10000000)); dir2num['U'] = pair(-1, 0); dir2num['L'] = pair( 0,-1); dir2num['D'] = pair(+1, 0); dir2num['R'] = pair( 0,+1); vector ans; Astar(); return 0; } //====================temp==================== #else #include using namespace std; #define REP(i, n) for (int i = 0; i < (int)(n); i++) #define RREP(i, n) for (int i = ((int)(n)-1); i >= 0; i--) #define REPITR(itr, ARRAY) for (auto itr = (ARRAY).begin(); itr != (ARRAY).end(); ++itr) #define RREPITR(itr, ARRAY) for (auto itr = (ARRAY).rbegin(); itr != (ARRAY).end(); ++itr) #define ALL(n) (n).begin(),(n).end() using ll = long long; using ull = unsigned long long; //#define int long long template struct edge{ int to; T cost; edge(){} edge(int to, T cost):to(to), cost(cost){} }; #endif