fork download
copy 
  1. /// Author : Nguyễn Thái Sơn - Ti20 - THPT chuyên Lương Thế Vinh
  2. /// Training VOI 2023
  3.  
  4. #include<bits/stdc++.h>
  5. //#include <ext/pb_ds/assoc_container.hpp>
  6. //#include <ext/pb_ds/trie_policy.hpp>
  7. //#include <ext/rope>
  8.  
  9. //#pragma GCC optimize("Ofast")
  10. //#pragma GCC optimization("unroll-loops, no-stack-protector")
  11. //#pragma GCC target("avx,avx2,fma")
  12.  
  13. //using namespace std;
  14. //using namespace __gnu_pbds;
  15. //using namespace __gnu_cxx;
  16.  
  17. #define fi first
  18. #define se second
  19. #define TASK "test"
  20. #define pb push_back
  21. #define EL cout << endl
  22. #define Ti20_ntson int main()
  23. #define in(x) cout << x << endl
  24. #define all(x) (x).begin(),(x).end()
  25. #define getbit(x, i) (((x) >> (i)) & 1)
  26. #define cntbit(x) __builtin_popcount(x)
  27. #define FOR(i,l,r) for (int i = l; i <= r; i++)
  28. #define FORD(i,l,r) for (int i = l; i >= r; i--)
  29. #define Debug(a,n) for (int i = 1; i <= n; i++) cout << a[i] << " "; cout << endl
  30.  
  31. using namespace std;
  32.  
  33. typedef long long ll;
  34. typedef vector<int> vi;
  35. typedef pair<int,int> vii;
  36. typedef unsigned long long ull;
  37. typedef vector<vector<int>> vvi;
  38.  
  39. const int N = 55;
  40. const int oo = INT_MAX;
  41. const int mod = 1e9 + 7;
  42. const int d4x[4] = {-1, 0, 1, 0} , d4y[4] = {0, 1, 0, -1};
  43. const int d8x[8] = {-1, -1, 0, 1, 1, 1, 0, -1}, d8y[8] = {0, 1, 1, 1, 0, -1, -1, -1};
  44.  
  45. int n, m, dp[N][N][N];
  46. char c[N][N];
  47. string s;
  48. vii st, ft;
  49.  
  50. inline void Read_Input() {
  51.     memset(dp, 0x3f, sizeof(dp));
  52.     cin >> n >> m;
  53.     FOR(i, 1, n)
  54.         FOR(j, 1, m) {
  55.             cin >> c[i][j];
  56.             if (c[i][j] == 'S')
  57.                 st = vii(i, j);
  58.             if (c[i][j] == 'G')
  59.                 ft = vii(i, j);
  60.         }
  61.     cin >> s;
  62. }
  63.  
  64. inline void Mn(int &u, int v) {
  65.     if (u > v) u = v;
  66. }
  67.  
  68. inline void Solve() {
  69.     dp[st.fi][st.se][0] = 0;
  70.     int Ans = mod;
  71.     #define t3 tuple<int, int, int>
  72.     FOR(i, 0, s.size()) {
  73.         priority_queue<t3, vector<t3>, greater<t3>> Q;
  74.         FOR(x, 1, n)
  75.             FOR(y, 1, m)
  76.                 Q.push({dp[x][y][i], x, y});
  77. //        cout << "CHECK " << i << endl;
  78.         while (Q.size()) {
  79.             auto[w, x, y] = Q.top(); Q.pop();
  80.             if (dp[x][y][i] < w) continue;
  81. //            cout << w << " " << x << " " << y << endl;
  82.             for (int k = 0; k < 4; k++) {
  83.                 int nx = x + d4x[k];
  84.                 int ny = y + d4y[k];
  85.                 if (nx < 1 || nx > n) continue;
  86.                 if (ny < 1 || ny > m) continue;
  87.                 if (c[nx][ny] == '#') continue;
  88. //                cout << "UPD " << nx << " " << ny << endl;
  89.                 if (dp[nx][ny][i] > w + 1) {
  90.                     dp[nx][ny][i] = w + 1;
  91.                     Q.push({w + 1, nx, ny});
  92.                 }
  93.             }
  94.         }
  95. //        cout << "MATRIX " << i << endl;
  96.         if (i < s.size())
  97.             FOR(x, 1, n)
  98.                 FOR(y, 1, m) {
  99. //                    cout << "CHECK " << x << " " << y << " " << dp[x][y][i] << endl;
  100.                     Mn(dp[x][y][i + 1], dp[x][y][i] + 1);
  101.                     int nx = x, ny = y;
  102.                     if (s[i] == 'U')
  103.                         nx--;
  104.                     if (s[i] == 'D')
  105.                         nx++;
  106.                     if (s[i] == 'L')
  107.                         ny--;
  108.                     if (s[i] == 'R')
  109.                         ny++;
  110. //                    cout << nx << " " << ny << endl;
  111.                     if (nx < 1 || nx > n) {
  112.                         Mn(dp[x][y][i + 1], dp[x][y][i]);
  113.                         continue;
  114.                     }
  115.                     if (ny < 1 || ny > m) {
  116.                         Mn(dp[x][y][i + 1], dp[x][y][i]);
  117.                         continue;
  118.                     }
  119.                     if (c[nx][ny] == '#')
  120.                         Mn(dp[x][y][i + 1], dp[x][y][i]);
  121.                     else Mn(dp[nx][ny][i + 1], dp[x][y][i]);
  122.                 }
  123.         Ans = min(Ans, dp[ft.fi][ft.se][i]);
  124.     }
  125.     cout << Ans;
  126. }
  127.  
  128. Ti20_ntson {
  129. //    freopen(TASK".INP","r",stdin);
  130. //    freopen(TASK".OUT","w",stdout);
  131.     ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  132.     int T = 1;
  133.     while (T -- ) {
  134.         Read_Input();
  135.         Solve();
  136.     }
  137. }
  138.  
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/UxwgbN
language:
C++14 (gcc 8.3)
created:
2 hours 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!