fork download
copy 
  1. #pragma GCC optimize("O2")
  2. #pragma GCC target("avx,avx2,fma")
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5. using ll = long long;
  6. const int mod = 1e9 + 7;
  7. #define el endl
  8. #define int int64_t
  9. #define fi first
  10. #define se second
  11. #define file(x) freopen(x".inp", "r", stdin); freopen(x".out", "w", stdout)
  12. #define pb push_back
  13. #define gd() ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr)
  14. #define rizzler signed main()
  15. #define tc() int t; cin >> t; while(t--)
  16. void tle() {
  17.     double time_taken = 1000.0 * clock() / CLOCKS_PER_SEC;
  18.  
  19.     if (time_taken < 1000.0) {
  20.         std::cerr << "Time: ";
  21.         std::cerr << time_taken << "ms" << std::string(27, '\t');
  22.     } else {
  23.         std::cerr << "TLE Warning!\n";
  24.         std::cerr << "Time: ";
  25.         std::cerr << (time_taken / 1000.0) << "s" << std::string(27, '\n');
  26.     }
  27. }
  28.  
  29. struct chess{
  30.     int i1, j1, i2, j2;
  31. };
  32.  
  33. int v[105][105], m[105][105], xv, yv, xm, ym, res, n;
  34. char a[105][105];
  35.  
  36. int dxv[] = {-1, 0, 1, -1, 0, 1, -1, 0, 1};
  37. int dyv[] = {-1, -1, -1, 0, 0, 0, 1, 1, 1};
  38.  
  39. int dxm[] = {-2, -1, 1, 2, 2, 1, -1, -2, 0};
  40. int dym[] = {-1, -2, -2, -1, 1, 2, 2, 1, 0};
  41.  
  42. bool valid(int i, int j){
  43.     return i >= 1 && i <= n && j >= 1 && j <= n && a[i][j] != '#';
  44. }
  45.  
  46. void bfs(){
  47.     v[xv][yv] = 0;
  48.     m[xm][ym] = 0;
  49.     queue<chess> q;
  50.     q.push({xv,yv,xm,ym});
  51.     for (int i = 0; i < 9; i++){
  52.         for (int j = 0; j < 9; j++){
  53.         int i1 = xv + dxv[i];
  54.         int j1 = yv + dyv[i];
  55.         int i2 = xm + dxm[j];
  56.         int j2 = ym + dym[j];
  57.         if (valid(i1,j1) && valid(i2,j2) && v[i1][j1] == 0 && m[i2][j2] == 0){
  58.             q.push({i1,j1,i2,j2});
  59.             if (i1 != xv && j1 != yv) v[i1][j1] = v[xv][yv] + 1;
  60.             if (i2 != xm && j2 != ym) m[i2][j2] = m[xm][ym] + 1;
  61.         }
  62.     }
  63. }
  64.     while(!q.empty()){
  65.         auto top = q.front(); q.pop();
  66.         int i1 = top.i1, j1 = top.j1, i2 = top.i2, j2 = top.j2;
  67.         if (i1 == i2 && j1 == j2) res = min(res, max(v[i1][j1], m[i2][j2]));
  68.         for (int i = 0; i < 9; i++){  
  69.             for (int j = 0; j < 9; j++){  
  70.                 int ni1 = i1 + dxv[i];
  71.                 int nj1 = j1 + dyv[i];
  72.                 int ni2 = i2 + dxm[j];
  73.                 int nj2 = j2 + dym[j];
  74.                 if (!valid(ni1,nj1) || !valid(ni2,nj2)) continue;
  75.                 if (v[ni1][nj1] != 0 && m[ni2][nj2] != 0) continue;
  76.                 if (v[ni1][nj1] == 0) v[ni1][nj1] = v[i1][j1] + 1;
  77.                 if (m[ni2][nj2] == 0) m[ni2][nj2] = m[i2][j2] + 1;
  78.                 q.push({ni1,nj1,ni2,nj2});
  79.                 if (ni1 == ni2 && nj1 == nj2)
  80.                     res = min(res, max(v[ni1][nj1], m[ni2][nj2]));
  81.             }
  82.         }
  83.     }
  84. }
  85.  
  86. rizzler{
  87.     gd();
  88.         cin >> n;
  89.         for (int i = 1; i <= n; i++){
  90.             for (int j = 1; j <= n; j++){
  91.                 cin >> a[i][j];
  92.                 if (a[i][j] == 'T'){
  93.                     xv = i, yv = j;
  94.                 } else if(a[i][j] == 'M'){
  95.                     xm = i, ym = j;
  96.                 }
  97.             }
  98.         }
  99.         res = 1e9;
  100.         bfs();
  101.         cout << res << "\n";
  102.  
  103.  
  104.  
  105.     tle();
  106.  
  107. }
Success #stdin #stdout #stderr 0.01s 5280KB
comments (?)
stdin
copy 
5
M....
.....
.#...
.#..#
...#T
stdout
copy 
3
stderr
copy 
Time: 4.468ms
https://ideone.com/GKAEvd
language:
C++ (gcc 8.3)
created:
19 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!