fork download
copy 
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <fstream>
  4. #include <deque>
  5. #include <algorithm>
  6. #include <utility>
  7. #include <vector>
  8. #include <cmath>
  9. #include <queue>
  10. #include <string>
  11. using namespace std;
  12.  
  13. #define in cin
  14. #define out cout
  15. #define REP(i,s,e) for(int i=s; i<=e; i++)
  16. #define isin(a,b,c) ( (a<=c)&&(c<=b) )
  17.  
  18. typedef pair<int, int> pii;
  19. typedef vector<pii> vpii;
  20.  
  21. char maze[12][12];
  22.  
  23. int dx[] = {-1, 1, 0, 0};
  24. int dy[] = {0, 0, -1, 1};
  25. pii moveto[4][12][12];
  26. int exit_x, exit_y;
  27.  
  28. char LRUD[] = "LRUD";
  29. char trace[12] = "";
  30. bool flag = false;
  31. int r, c;
  32.  
  33. void foo(vpii ball, int cnt, int previous_dir)
  34. {
  35.     int ballsize = ball.size();
  36.  
  37.     if(cnt > 11 || flag) return;
  38.     if(ball.size() == 1 && ball[0].first == exit_x && ball[0].second == exit_y && flag == false)
  39.     {
  40.         flag = true;
  41.         REP(i,0,cnt-1) out << trace[i];
  42.         out << endl;
  43.         return;
  44.     }
  45.  
  46.     REP(i,0,3)
  47.     {
  48.         if(previous_dir == i) continue;
  49.  
  50.         int chk[12][12];
  51.         REP(ii,1,r)
  52.         {
  53.             REP(jj,1,c)
  54.             {
  55.                 chk[ii][jj] = 0;
  56.             }
  57.         }
  58.         vpii mball;
  59.         REP(j,0,ball.size()-1)
  60.         {
  61.             //out << ball[j].first << " " << ball[j].second << endl;
  62.             pii _T = moveto[i][ ball[j].first ][ ball[j].second ];
  63.             //out << _T.first << " " << _T.second << endl;
  64.             if(chk[_T.first][_T.second] == 0)
  65.             {
  66.                 chk[_T.first][_T.second] = 1;
  67.                 mball.push_back(_T);
  68.             }
  69.         }
  70.  
  71.         trace[cnt] = LRUD[i];
  72.         foo(mball, cnt+1, i);
  73.     }
  74. }
  75.  
  76. int main()
  77. {
  78.     //freopen("in.txt", "r+", stdin);
  79.     ios::sync_with_stdio(false);
  80.  
  81.     int tc; in >> tc;
  82.     while(tc--)
  83.     {
  84.         flag = false;
  85.  
  86.         in >> r >> c;
  87.         REP(i,1,r) REP(j,1,c) in >> maze[i][j];
  88.  
  89.         vpii ball;
  90.         REP(i,1,r) REP(j,1,c)
  91.         {
  92.             if(maze[i][j] == 'O') {exit_x = i; exit_y = j;}
  93.             else if(maze[i][j] == '.') ball.push_back( make_pair(i,j) );
  94.         }
  95.  
  96.         REP(i,0,r+1) REP(j,1,c+1)
  97.             if(i == 0 || j == 0 || i == r+1 || j == c+1 ) maze[i][j] = '#';
  98.  
  99.         REP(i,1,r) REP(j,1,c)
  100.         {
  101.             if(maze[i][j] == '.')
  102.             {
  103.                 REP(m,0,3)
  104.                 {
  105.                     int px = j + dx[m];
  106.                     int py = i + dy[m];
  107.  
  108.                     while(maze[py][px] == '.')
  109.                     {
  110.                         px += dx[m];
  111.                         py += dy[m];
  112.                     }
  113.  
  114.                     if(maze[py][px] == '#')
  115.                         moveto[m][i][j] = make_pair(py-dy[m], px-dx[m]);
  116.                     else if(maze[py][px] == 'O')
  117.                         moveto[m][i][j] = make_pair(py, px);
  118.  
  119.                     //out << LRUD[m] << " " << i << " " << j << " " << moveto[m][i][j].first << " " << moveto[m][i][j].second << endl;
  120.                 }
  121.             }
  122.             else
  123.             {
  124.                 REP(m,0,3)
  125.                 {
  126.                     moveto[m][i][j] = make_pair(0,0);
  127.                 }
  128.             }
  129.         }
  130.  
  131.         foo(ball, 1, -1);
  132.  
  133.         if(!flag) out << "XHAE" << endl;
  134.     } // END OF A TESTCASE
  135.  
  136.     return 0;
  137. }
  138.  
Success #stdin #stdout 0.13s 3484KB
comments (?)
stdin
copy 
3 5 5
#####
#...O
#.#.#
#...#
#####
10 10
#O########
#...######
###.######
#...######
#.########
#...###..#
###.####.#
###......#
##########
##########
3 5
#####
#...#
##O##
stdout
copy 
LRLRLRLRUR
RDLULURULU
XHAE
https://ideone.com/ZiHsjE
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!