Guest User

Untitled

a guest
May 27th, 2017
227
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define SF(x) scanf("%I64d",&x)
  3. #define F first
  4. #define S second
  5. #define MEM(a,b) memset(a,b,sizeof(a))
  6. #define DB(x) cout << #x << " is " << x << endl
  7. #define ffs(x) __builtin_ffs(x) // This function returns 1 + least significant 1-bit of x. If x == 0, returns 0. Here x is int, this function with suffix 'l' gets a long argument and with suffix 'll' gets a long long argument.
  8. #define clz(x) __builtin_clz(x) // This function returns number of leading 0-bits of x which starts from most significant bit position. x is unsigned int and like previous function this function with suffix 'l gets a unsigned long argument and with suffix 'll' gets a unsigned long long argument. If x == 0, returns an undefined value.
  9. #define ctz(x) __builtin_ctz(x) // This function returns number of trailing 0-bits of x which starts from least significant bit position. x is unsigned int and like previous function this function with suffix 'l' gets a unsigned long argument and with suffix 'll' gets a unsigned long long argument. If x == 0, returns an undefined value.
  10. #define popcount(x) __builtin_popcount(x) // This function returns number of active bits in the binary represintation of the number
  11. #define pb push_back
  12.  
  13. using namespace std;
  14. typedef long long ll;
  15.  
  16. int dx[] = {1, -1, 0, 0};
  17. int dy[] = {0, 0, 1, -1};
  18.  
  19. ll Mypow(ll X,ll Y){
  20. if(Y < 0)return 0;
  21. if(Y == 0)return 1;
  22. if(Y == 1){
  23. return X;
  24. }
  25. else{
  26. ll x = Mypow(X ,Y / 2);
  27. x *= x;
  28. if(Y % 2)
  29. return (x * X);
  30. else
  31. return x;
  32. }
  33. }
  34.  
  35. int FX, FY;
  36. char Down = 'D', Up = 'U', Left = 'L', Right = 'R';
  37. int n, m;
  38. char a[110][110];
  39. int pos_x, pos_y, temp_x, temp_y;
  40.  
  41. bool check(int x, int y)
  42. {
  43. if(x > n || x < 1 || y > m || y < 1 || a[x][y] == '*')
  44. return false;
  45. return true;
  46. }
  47.  
  48. void BFS(int start_x, int start_y)
  49. {
  50. bool vis[110][110];
  51. pair < int , int > par[110][110];
  52. memset(vis, 0, sizeof(vis));
  53. memset(par, 0, sizeof(par));
  54. queue < pair < pair < int , int > , pair < int , int > > > Q;
  55. Q.push({{start_x, start_y}, {-1, -1}});
  56. while(!Q.empty()){
  57. pair < pair < int , int > , pair < int , int > > u = Q.front();
  58. Q.pop();
  59. if(!check(u.F.F, u.F.S)){
  60. continue;
  61. }
  62. if(vis[u.F.F][u.F.S]){
  63. continue;
  64. }
  65. vis[u.F.F][u.F.S] = true;
  66. par[u.F.F][u.F.S] = {u.S.F, u.S.S};
  67. for(int i = 0 ; i < 4 ; i++){
  68. Q.push({{u.F.F + dx[i], u.F.S + dy[i]}, {u.F.F, u.F.S}});
  69. }
  70. }
  71. int x = FX;
  72. int y = FY;
  73. string s = "";
  74. while(x != -1 && y != -1){
  75. if(par[x][y].F == x - 1){
  76. s += Down;
  77. }
  78. if(par[x][y].F == x + 1){
  79. s += Up;
  80. }
  81. if(par[x][y].S == y + 1){
  82. s += Left;
  83. }
  84. if(par[x][y].S == y - 1){
  85. s += Right;
  86. }
  87. int temp1 = par[x][y].F, temp2 = par[x][y].S;
  88. x = temp1, y = temp2;
  89. }
  90. reverse(s.begin(), s.end());
  91. for(int i = 0 ; i < s.size() ; i++){
  92. cout << s[i] << endl;
  93. cin >> x >> y;
  94. }
  95. return;
  96. }
  97.  
  98. int main()
  99. {
  100. cin >> n >> m;
  101. for(int i = 1 ; i <= n ; i++){
  102. for(int j = 1 ; j <= m ; j++){
  103. cin >> a[i][j];
  104. if(a[i][j] == 'F'){
  105. FX = i;
  106. FY = j;
  107. }
  108. }
  109. }
  110. if(a[2][1] != '*'){
  111. cout << Down << endl;
  112. cin >> pos_x >> pos_y;
  113. if(pos_x == FX && FY == pos_y){
  114. return 0;
  115. }
  116. if(pos_x == 1 && pos_y == 1){
  117. swap(Down, Up);
  118. }
  119. cout << Up << endl;
  120. cin >> pos_x >> pos_y;
  121. while(a[pos_x][pos_y + 1] == '*'){
  122. cout << Down << endl;
  123. cin >> pos_x >> pos_y;
  124. if(pos_x == FX && pos_y == FY){
  125. return 0;
  126. }
  127. }
  128. if(a[pos_x][pos_y + 1] != '*'){
  129. cout << Right << endl;
  130. cin >> temp_x >> temp_y;
  131. if(temp_x == FX && FY == temp_y){
  132. return 0;
  133. }
  134. if(pos_x == temp_x && pos_y == temp_y){
  135. swap(Left, Right);
  136. }
  137. pos_x = temp_x, pos_y= temp_y;
  138. }
  139. }
  140. else{
  141. cout << Right << endl;
  142. cin >> pos_x >> pos_y;
  143. if(pos_x == FX && FY == pos_y){
  144. return 0;
  145. }
  146. if(pos_x == 1 && pos_y == 1){
  147. swap(Left, Right);
  148. }
  149. cout << Left << endl;
  150. cin >> pos_x >> pos_y;
  151. while(a[pos_x + 1][pos_y] == '*'){
  152. cout << Right << endl;
  153. cin >> pos_x >> pos_y;
  154. if(pos_x == FX && pos_y == FY){
  155. return 0;
  156. }
  157. }
  158. if(a[pos_x + 1][pos_y] != '*'){
  159. cout << Down << endl;
  160. cin >> temp_x >> temp_y;
  161. if(temp_x == FX && FY == temp_y){
  162. return 0;
  163. }
  164. if(pos_x == temp_x && pos_y == temp_y){
  165. swap(Up, Down);
  166. }
  167. pos_x = temp_x, pos_y = temp_y;
  168. }
  169. }
  170. BFS(pos_x, pos_y);
  171. return 0;
  172. }
RAW Paste Data