fork download
copy 
  1. // #pragma GCC optimize("O3", "unroll-loops")
  2. // #pragma GCC target("avx2", "bmi", "bmi2", "lzcnt", "popcnt")
  3.  
  4. #include <bits/stdc++.h>
  5. #define ldb long double
  6. //#define double ldb
  7. #define db double
  8. #define unomap unordered_map
  9. #define unoset unordered_set
  10. #define endl '\n'
  11. #define str string
  12. #define strstr stringstream
  13. #define sz(a) (int)a.size()
  14. #define ll long long
  15. // #define int ll
  16. #define pii pair <int, int>
  17. #define pll pair <ll, ll>
  18. #define Unique(a) a.resize(unique(all(a)) - a.begin())
  19. #define ull unsigned long long
  20. #define fir first
  21. #define sec second
  22. #define idc cin.ignore()
  23. #define lb lower_bound
  24. #define ub upper_bound
  25. #define all(s) s.begin(), s.end()
  26. #define rall(s) s.rbegin(), s.rend()
  27. #define rev reverse
  28. #define gcd __gcd
  29. #define pushb push_back
  30. #define popb pop_back
  31. #define pushf push_front
  32. #define popf pop_front
  33. #define emp emplace
  34. #define empb emplace_back
  35. #define mul2x(a, x) a << x
  36. #define div2x(a, x) a >> x
  37. #define lcm(a, b) (a / __gcd(a, b) * b)
  38. #define log_base(x, base) log(x) / log(base)
  39. #define debug cerr<<"No errors!",exit(0);
  40. #define forw(i, a, b)  for (int i = a; i <= b; ++i)
  41. #define forw2(i, a, b) for (ll i = a; i <= b; ++i)
  42. #define fors(i, a, b)  for (int i = a; i >= b; --i)
  43. #define fors2(i, a, b) for (ll i = a; i >= b; --i)
  44. #define pqueue priority_queue
  45. #define sqrt sqrtl
  46. #define i128 __int128
  47. #define popcount __builtin_popcountll
  48. #define BIT(x, i) (((x) >> (i)) & 1)
  49. #define MASK(x) ((1LL) << (x))
  50. #define want_digit(x) cout << fixed << setprecision(x);
  51. #define excuting_time 1000.0 * clock() / CLOCKS_PER_SEC
  52. #define mapa make_pair
  53. using namespace std;
  54. const int MOD = 1e9 + 7; // 998244353;
  55. const int inf = 1e9;
  56. const ll INF = 1e18; // MASK(63) - 1
  57. const int limN = 1e4 + 5;
  58. const int dx[] = {-1, 0, 0, 1};
  59. const int dy[] = {0, -1, 1, 0};
  60.  
  61. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  62. inline ll random(const ll &L, const ll &R) {
  63.     return uniform_int_distribution<ll> (L, R) (rng);
  64. }
  65.  
  66. /* -------~~~~~~===== END OF TEMPLATE =====~~~~~~------- */
  67.  
  68.  
  69.  
  70. int n, m, k;
  71. pii light[limN];
  72. vector <int> row[limN], col[limN];
  73. map <pii, int> f;
  74. map <pii, bool> lighted;
  75. void solve() {
  76.     cin >> n >> m >> k;
  77.     forw (i, 1, k) {
  78.         int r, c; cin >> r >> c;
  79.         light[i] = {r, c};
  80.         row[r].pushb(i); col[c].pushb(i);
  81.         lighted[mapa(r, c)] = true;
  82.     }
  83.  
  84.     #define T tuple <int, int, int>
  85.     pqueue <T, vector <T>, greater <T>> pq;
  86.     f[{1, 1}] = 0; pq.emp(0, 1, 1);
  87.     while (!pq.empty()) {
  88.         int dis, r, c;
  89.         tie(dis, r, c) = pq.top(); pq.pop();
  90.         if (dis > f[{r, c}]) continue;
  91.         cout << r << " " << c << " " << dis << endl;
  92.  
  93.         // không mua đuốc
  94.         forw (i, 0, 3) {
  95.             int _r = r + dx[i], _c = c + dy[i];
  96.             if (_r < 1 || _r > n || _c < 1 || _c > m) continue;
  97.             if (lighted.count(mapa(_r, _c)) 
  98.             && (!f.count(mapa(_r, _c)) || f[mapa(_r, _c)] > dis)) {
  99.                 f[mapa(_r, _c)] = dis;
  100.                 pq.emp(dis, _r, _c);
  101.             }
  102.         }
  103.  
  104.  
  105.         // mua đuốc
  106.         forw (i, -1, 1) {
  107.             int _r = r + i;
  108.             if (_r > n || _r < 1) continue;
  109.             for (int id : row[_r]) {
  110.                 pii cur = light[id];
  111.                 if (!f.count(cur) || f[cur] > dis + 1) {
  112.                     f[cur] = dis + 1;
  113.                     pq.emp(dis + 1, cur.fir, cur.sec);
  114.                 }
  115.             }
  116.             if (_r == n) {
  117.                 pii cur = mapa(n, m);
  118.                 if (!f.count(cur) || f[cur] > dis + 1) {
  119.                     f[cur] = dis + 1;
  120.                     pq.emp(dis + 1, cur.fir, cur.sec);
  121.                 }
  122.             }
  123.         }
  124.  
  125.         forw (i, -1, 1) {
  126.             int _c = r + i;
  127.             if (_c > m || _c < 1) continue;
  128.             for (int id : col[_c]) {
  129.                 pii cur = light[id];
  130.                 if (!f.count(cur) || f[cur] > dis + 1) {
  131.                     f[cur] = dis + 1;
  132.                     pq.emp(dis + 1, cur.fir, cur.sec);
  133.                 }
  134.             }
  135.             if (_c == m) {
  136.                 pii cur = mapa(n, m);
  137.                 if (!f.count(cur) || f[cur] > dis + 1) {
  138.                     f[cur] = dis + 1;
  139.                     pq.emp(dis + 1, cur.fir, cur.sec);
  140.                 }
  141.             }
  142.         }
  143.     }
  144.  
  145.     if (f.count(mapa(n, m))) 
  146.         cout << f[mapa(n, m)] << endl;
  147.     else cout << "-1\n";
  148. }
  149.  
  150. signed main() {
  151.     ios::sync_with_stdio(false), cin.tie(nullptr);
  152.     srand(time(NULL));
  153.     #define name "test"
  154.     if (fopen(name".INP", "r")) {
  155.         freopen(name".INP", "r", stdin);
  156.         freopen(name".OUT", "w", stdout);
  157.     }
  158.     bool testCase = false;
  159.     int numTest = 1;
  160.     // cin >> numTest;
  161.     forw (i, 1, numTest) {
  162.         if (testCase) cout << "Case #" << i << ": ";
  163.         solve();
  164.     }
  165.     return 0;
  166. }
  167.  
  168.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
4 4 5
1 1
2 1
2 3
3 3
4 3
stdout
copy 
1 1 0
2 1 0
2 3 1
3 3 1
4 3 1
4 4 2
2
https://ideone.com/amX7mw
language:
C++14 (gcc 8.3)
created:
3 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!