fork download
copy 
  1. #pragma GCC optimize("Ofast")
  2. #include <bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. #define ll long long
  7. #define pb push_back
  8. #define mp make_pair
  9. #define mogaAc ios_base::sync_with_stdio(false);
  10. #define fi first
  11. #define nd second
  12. int arr[1005][1005];
  13. bool visited[1005][1005];
  14. int cost[1005][1005];
  15. int n, m;
  16.  
  17. void bfs(int i, int j)
  18. {
  19.     deque<pair<int, int>> urutan;
  20.     urutan.push_back({i, j});
  21.     visited[i][j] = true;
  22.     cost[i][j] = 0;
  23.     int letaki, letakj;
  24.     while (!urutan.empty())
  25.     {
  26.         letaki = urutan.front().first;
  27.         letakj = urutan.front().second;
  28.         urutan.pop_front();
  29.  
  30.         if (arr[letaki][letakj] == 2)
  31.         {
  32.             cout << "YES" << endl;
  33.             cout << cost[letaki][letakj] << endl;
  34.             string path = "";
  35.             int jarak2 = cost[letaki][letakj];
  36.             int now1 = letaki;
  37.             int now2 = letakj;
  38.  
  39.             while (jarak2 > 1)
  40.             {
  41.                 if (now1 + 1 < n && cost[now1 + 1][now2] == jarak2 - 1 && arr[now1 + 1][now2] != 0)
  42.                 {
  43.                     path = "U" + path;
  44.                     now1++;
  45.                 }
  46.                 else if (now1 - 1 >= 0 && cost[now1 - 1][now2] == jarak2 - 1 && arr[now1 - 1][now2] != 0)
  47.                 {
  48.                     path = "D" + path;
  49.                     now1--;
  50.                 }
  51.                 else if (now2 + 1 < m && cost[now1][now2 + 1] == jarak2 - 1 && arr[now1][now2 + 1] != 0)
  52.                 {
  53.                     path = "L" + path;
  54.                     now2++;
  55.                 }
  56.                 else if (now2 - 1 >= 0 && cost[now1][now2 - 1] == jarak2 - 1 && arr[now1][now2 - 1] != 0)
  57.                 {
  58.                     path = "R" + path;
  59.                     now2--;
  60.                 }
  61.                 jarak2--;
  62.             }
  63.             if (now1 + 1 < n && cost[now1 + 1][now2] == jarak2 - 1 && arr[now1 + 1][now2] == 3)
  64.             {
  65.                 path = "U" + path;
  66.                 now1++;
  67.             }
  68.             else if (now1 - 1 >= 0 && cost[now1 - 1][now2] == jarak2 - 1 && arr[now1 - 1][now2] == 3)
  69.             {
  70.                 path = "D" + path;
  71.                 now1--;
  72.             }
  73.             else if (now2 + 1 < m && cost[now1][now2 + 1] == jarak2 - 1 && arr[now1][now2 + 1] == 3)
  74.             {
  75.                 path = "L" + path;
  76.                 now2++;
  77.             }
  78.             else if (now2 - 1 >= 0 && cost[now1][now2 - 1] == jarak2 - 1 && arr[now1][now2 - 1] == 3)
  79.             {
  80.                 path = "R" + path;
  81.                 now2--;
  82.             }
  83.             cout << path << endl;
  84.             exit(0);
  85.         }
  86.  
  87.         if (letaki + 1 < n && arr[letaki + 1][letakj] > 0 && !visited[letaki + 1][letakj])
  88.         {
  89.             urutan.push_back({letaki + 1, letakj});
  90.             cost[letaki + 1][letakj] = cost[letaki][letakj] + 1;
  91.             visited[letaki + 1][letakj] = true;
  92.         }
  93.         if (letaki - 1 >= 0 && arr[letaki - 1][letakj] > 0 && !visited[letaki - 1][letakj])
  94.         {
  95.             urutan.push_back({letaki - 1, letakj});
  96.             cost[letaki - 1][letakj] = cost[letaki][letakj] + 1;
  97.             visited[letaki - 1][letakj] = true;
  98.         }
  99.         if (letakj + 1 < m && arr[letaki][letakj + 1] > 0 && !visited[letaki][letakj + 1])
  100.         {
  101.             urutan.push_back({letaki, letakj + 1});
  102.             cost[letaki][letakj + 1] = cost[letaki][letakj] + 1;
  103.             visited[letaki][letakj + 1] = true;
  104.         }
  105.         if (letakj - 1 >= 0 && arr[letaki][letakj - 1] > 0 && !visited[letaki][letakj - 1])
  106.         {
  107.             urutan.push_back({letaki, letakj - 1});
  108.             cost[letaki][letakj - 1] = cost[letaki][letakj] + 1;
  109.             visited[letaki][letakj - 1] = true;
  110.         }
  111.     }
  112.  
  113.     cout << "NO" << endl;
  114.     return;
  115. }
  116.  
  117. int main()
  118. {
  119.     mogaAc;
  120.     cin.tie(NULL);
  121.     cout.tie(NULL);
  122.  
  123.     cin >> n >> m;
  124.  
  125.     int Awali = 0;
  126.     int Awalj = 0;
  127.     int letakB1 = 0;
  128.     int letakB2 = 0;
  129.     for (int i = 0; i < n; i++)
  130.     {
  131.         for (int j = 0; j < m; j++)
  132.         {
  133.             char a;
  134.             cin >> a;
  135.             if (a == '.')
  136.             {
  137.                 arr[i][j] = 1;
  138.             }
  139.             if (a == 'A')
  140.             {
  141.                 arr[i][j] = 3;
  142.                 Awali = i;
  143.                 Awalj = j;
  144.             }
  145.             if (a == 'B')
  146.             {
  147.                 arr[i][j] = 2;
  148.                 letakB1 = i;
  149.                 letakB2 = j;
  150.             }
  151.         }
  152.     }
  153.     if ((arr[letakB1 + 1][letakB2] == 0 || letakB1 + 1 >= n) && (arr[letakB1 - 1][letakB2] == 0 || letakB1 - 1 < 0) && (arr[letakB1][letakB2 + 1] == 0 || letakB2 + 1 >= m) && (arr[letakB1][letakB2 - 1] == 0 || letakB2 < 0))
  154.     {
  155.         cout << "NO" << endl;
  156.         return 0;
  157.     }
  158.     bfs(Awali, Awalj);
  159.     return 0;
  160. }
  161. // int main()
  162. // {
  163. //     vector<int> a;
  164. //     a.pb(4);
  165. //     a.pb(5);
  166. //     a.pb(8);
  167. //     a.pb(7);
  168. //     vector<int> b;
  169. //     b = a;
  170. //     for (int i = 0; i < b.size(); i++)
  171. //     {
  172. //         cout << b[i] << endl;
  173. //     }
  174. // }
  175.  
  176. // arrayy------------------------------------------------------
  177. //  buat ngecek array 1 apakah sama dengan array 2:
  178. //   bool sama = equal(arr, arr + size, arr1);
  179. //   buat ngecek besar dari array:
  180. //   int size = sizeof(arr) / sizeof(arr[0]);
  181. // indexke LowerBound/upperbound
  182. // auto it = upper_bound(arr.begin(), arr.end(), x);
  183. // int index = distance(arr.begin(), it);
  184. // cara cepet buat sorting-------------------------------------
  185. // dari kecil ke besar : sort(arr.begin(), arr.end());
  186. // dari besar ke kecil : sort(arr.begin(), arr.end(), greater<int>());
  187. // logaritma
  188. // anggap a=base, b=yang ingin di log, seperti logA (B)
  189. // rumus : log(b)/log(a)
  190. // Statitiska
  191. // menghitung rata rata data tambahan baru
  192. // R0 * (S0/S1) + (Data baru)/S1
  193. // R = Rata rata
  194. // S = Banyak data
  195. // 0 = yang lama
  196. // 1 = yang baru
  197. // ArrayGACORBINSERT (KALAU ELEMENTNYA CUMA 1)
  198. // set atau map
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
NO
https://ideone.com/GEir5h
language:
C++ (gcc 8.3)
created:
17 days 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!