fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. #define ll long long
  5. #define all(name)  name.begin(),name.end()
  6. #define rall(name)  name.rbegin(),name.rend()
  7. #define sz(s) (int)s.size()
  8. int dx[]{1, -1, 0, 0, 1, 1, -1, -1};
  9. int dy[]{0, 0, 1, -1, 1, -1, 1, -1};
  10.  
  11. void fast() {
  12.     std::ios_base::sync_with_stdio(0);
  13.     cin.tie(0);
  14.     cout.tie(0);
  15. }
  16.  
  17. ll n, m;
  18. vector<vector<ll>> v;
  19. ll vis[40][40][40][40];
  20. struct node {
  21.     ll x, y, sx, sy, d;
  22. };
  23.  
  24. bool valid(node t) {
  25.     return (t.x >= 0 && t.x < n && t.y >= 0 && t.y < m &&
  26.             abs(t.sx) < 4 && abs(t.sy) < 4 && v[t.x][t.y] &&
  27.             !vis[t.x][t.y][t.sx + 3][t.sy + 3]);
  28. }
  29.  
  30. void solve() {
  31.     cin >> n >> m;
  32.     v.resize(n + 2, vector<ll>(m + 2, 1LL));
  33.     memset(vis, 0, sizeof(vis));
  34.     pair<ll, ll> s, t;
  35.     ll p, x1, x2, y1, y2;
  36.     cin >> s.first >> s.second >> t.first >> t.second >> p;
  37.     while (p--) {
  38.         cin >> x1 >> x2 >> y1 >> y2;
  39.         for (int i = x1; i <= x2; i++)
  40.             for (int j = y1; j <= y2; j++)
  41.                 v[i][j] = 0;
  42.     }
  43.     ll ans = -1, tsx, tsy, tx, ty;
  44.     queue<node> q;
  45.     q.push({s.first, s.second, 0, 0, 0});
  46.     while (!q.empty()) {
  47.         node pp = q.front();
  48.         q.pop();
  49.         if (t == make_pair(pp.x, pp.y)) {
  50.             ans = pp.d;
  51.             break;
  52.         }
  53.         for (int i = 0; i < 9; i++) {
  54.             tsx = pp.sx + dx[i];
  55.             tsy = pp.sy + dy[i];
  56.             tx = pp.x + tsx;
  57.             ty = pp.y + tsy;
  58.             node temp = {tx, ty, tsx, tsy, pp.d + 1};
  59.             if (valid(temp)) {
  60.                 vis[tx][ty][tsx + 3][tsy + 3] = 1;
  61.                 q.push(temp);
  62.             }
  63.         }
  64.     }
  65.     if (ans == -1)
  66.         cout << "No solution.\n";
  67.     else
  68.         cout << "Optimal solution takes " << ans << " hops.\n";
  69. }
  70.  
  71. int main() {
  72.     fast();
  73.     int T = 1;
  74.     cin >> T;
  75.     while (T--) {
  76.         solve();
  77.     }
  78.     return 0;
  79. }
Success #stdin #stdout 0.01s 23656KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Optimal solution takes 0 hops.
https://ideone.com/V4l9UK
language:
C++ (gcc 8.3)
created:
41 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!