Advertisement
BaoJIaoPisu

Untitled

Aug 5th, 2021
103
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.03 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. #define pb push_back
  5. #define pf push_front
  6. #define popb pop_back
  7. #define popf pop_front
  8. #define ins insert
  9. #define pq priority_queue
  10. #define minele min_element
  11. #define maxele max_element
  12. #define lb lower_bound //first pos >= val
  13. #define ub upper_bound // first pos > val
  14. #define cnt_bit __builtin_popcount
  15. #define debug(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
  16. //#pragma GCC optimize("Ofast")
  17. //#pragma GCC target("avx,avx2,fma")
  18. using namespace std;
  19.  
  20. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  21.  
  22. typedef long long ll;
  23. typedef pair<ll, ll> pll;
  24. typedef pair<int, int> pii;
  25.  
  26.  
  27. int d4x[4] = {1, 0, -1, 0}; int d4y[4] = {0, 1, 0, -1};
  28. char go[4] = {'D', 'R', 'U', 'L'};
  29. int d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1};
  30. int d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1};
  31.  
  32. const ll oo = 1e18;
  33. const ll maxN = 20;
  34.  
  35. /* Author : Le Ngoc Bao Anh, 10A5, LQD High School for Gifted Student */
  36.  
  37. void maximize(int &a, int b) {
  38.     a = max(a, b);
  39. }
  40.  
  41. void minimize(int &a, int b) {
  42.     a = min(a, b);
  43. }
  44.  
  45. int p[maxN][maxN];
  46. int pre[maxN][maxN];
  47. bool vs[maxN][maxN][maxN][maxN], dp[maxN][maxN];
  48. struct G {
  49.     int id, a, b, c, d;
  50. } f[maxN][maxN][maxN][maxN];           
  51.  
  52. void solve() {
  53.     int n, m;
  54.     int a, b, c, d;
  55.     cin >> n >> m >> a >> b >> c >> d;
  56.     int blocks = 0;
  57.     a++; b++; c++; d++;
  58.     for(int i = 1; i <= n; i++) {
  59.         for(int j = 1; j <= m; j++) {
  60.             cin >> p[i][j];
  61.             blocks += p[i][j];
  62.         }
  63.     }
  64.  
  65.     auto is = [&](int x, int y) -> bool {
  66.         return (x >= 1 && y >= 1 && x <= n && y <= m && !p[x][y]);
  67.     };
  68.  
  69.     auto sub1 = [&]() -> void {
  70.         cout << 4 << endl;
  71.         cout << "ULUL";
  72.         return;
  73.     };
  74.  
  75.     auto sub2 = [&]() -> void {
  76.         queue<pii> q;
  77.         q.push(make_pair(a, b));
  78.         dp[a][b] = 1;
  79.         while(!q.empty()) {
  80.             int x = q.front().fi, y = q.front().se; q.pop();
  81.             for(int r = 0; r < 4; r++) {
  82.                 int nx = x + d4x[r], ny = y + d4y[r];
  83.                 if(!is(nx, ny)) continue;
  84.                 if(dp[nx][ny]) continue;
  85.                 dp[nx][ny] = true;
  86.                 pre[nx][ny] = r + 1;
  87.                 q.push(make_pair(nx, ny));
  88.             }
  89.         }
  90.  
  91.         vector<char> ans;
  92.         int x = 1, y = 1;
  93.         while(true) {
  94.             if(!pre[x][y]) break;
  95.             int k = pre[x][y] - 1;
  96.             ans.pb(go[k]);
  97.             x = x - d4x[k], y = y - d4y[k];
  98.         }
  99.  
  100.         int len = ans.size();
  101.         cout << len << endl;
  102.         reverse(ans.begin(), ans.end());
  103.         for(int i = 0; i < len; i++) {
  104.             cout << ans[i];
  105.         }
  106.     };
  107.  
  108.     auto sub3 = [&]() -> void {
  109.         cout << 20 << endl;
  110.         for(int i = 1; i <= 10; i++) cout << "U";
  111.         for(int i = 1; i <= 10; i++) cout << "L";
  112.     };
  113.  
  114.     auto sub4 = [&]() -> void {
  115.         struct P {
  116.             int a, b, c, d;
  117.         };
  118.         queue<P> q;
  119.         q.push({a, b, c, d});
  120.         vs[a][b][c][d] = true;
  121.         while(!q.empty()) {
  122.             int a = q.front().a, b = q.front().b, c = q.front().c, d = q.front().d; q.pop();
  123.             for(int r = 0; r < 4; r++) {
  124.                 int na = a + d4x[r], nb = b + d4y[r];
  125.                 int nc = c + d4x[r], nd = d + d4y[r];
  126.                 if(!is(na, nb)) na = a, nb = b;
  127.                 if(!is(nc, nd)) nc = c, nd = d;
  128.                 if(vs[na][nb][nc][nd]) continue;
  129.                 vs[na][nb][nc][nd] = true;
  130.                 f[na][nb][nc][nd] = {r + 1, a, b, c, d};
  131.                 q.push({na, nb, nc, nd});
  132.             }
  133.         }
  134.  
  135.         int a = 1, b = 1, c = 1, d = 1;
  136.         vector<char> ans;
  137.         while(true) {
  138.             if(!f[a][b][c][d].id) break;
  139.             G k = f[a][b][c][d];
  140.             ans.pb(go[k.id - 1]);
  141.             a = k.a, b = k.b;
  142.             c = k.c, d = k.d;
  143.         }
  144.  
  145.         int len = ans.size();
  146.         cout << len << endl;
  147.         reverse(ans.begin(), ans.end());
  148.         for(int i = 0; i < len; i++) cout << ans[i];
  149.     };
  150.  
  151.     auto sub5 = [&]() -> void {
  152.  
  153.     };
  154.  
  155.     if(n <= 2 && m <= 2) sub1();
  156.     else if(a == c && b == d) sub2();
  157.     else if(n <= 10 && m <= 10 && blocks == 0) sub3();
  158.     else if(n <= 10 && m <= 10) sub4();
  159.     else sub5();
  160. }
  161.  
  162. int main()
  163. {
  164.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  165.     #ifndef ONLINE_JUDGE
  166.     freopen("input.txt", "r", stdin);
  167.     freopen("output.txt", "w", stdout);
  168.     #else
  169.     //online
  170.     #endif
  171.  
  172.     int tc = 1, ddd = 0;
  173.     // cin >> tc;
  174.     while(tc--) {
  175.         //ddd++;
  176.         //cout << "Case #" << ddd << ": ";
  177.         solve();
  178.     }
  179. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement