fork(1) download
copy 
  1. // In the name of Allah.
  2. // "And He is with you wherever you are"..
  3.  
  4.  
  5. //#include <bits/stdc++.h>
  6. #include <iostream>
  7. #include <cmath>
  8. #include <string>
  9. #include <string.h>
  10. #include <stdlib.h>
  11. #include <algorithm>
  12. #include <iomanip>
  13. #include <assert.h>
  14. #include <vector>
  15. #include <cstring>
  16. #include <map>
  17. #include <deque>
  18. #include <queue>
  19. #include <stack>
  20. #include <sstream>
  21. #include <cstdio>
  22. #include <cstdlib>
  23. #include <ctime>
  24. #include <set>
  25. #include <complex>
  26. #include <unordered_map>
  27. #include <unordered_set>
  28. #include <list>
  29. #include <climits>
  30. #include <cctype>
  31. #include <bitset>
  32. #include <numeric>
  33. #include <array>
  34. #include <tuple>
  35. #include <stdexcept>
  36. #include <utility>
  37. #include <functional>
  38. #include <locale>
  39. #define mp make_pair
  40. #define pb push_back
  41. #define IO ios_base::sync_with_stdio(0);	cin.tie(0);	cout.tie(0);
  42. #define sz size()
  43. #define vi vector<int>
  44. #define vll vector<ll>
  45. #define vs vector<string>
  46. #define all(v) ((v).begin()), ((v).end())
  47. #define mms(Arr, Value) memset(Arr, Value, sizeof(Arr))
  48. #define vpii vector<pair<int, int> >
  49. #define vpll vector<pair<ll, ll> >
  50. #define pll pair<ll, ll>
  51. #define pii pair<int,int>
  52. #define re return
  53. #define fri(x,n)	for(int i = x ; i < n ; ++i)
  54. #define frj(x,n)	for(int j = x ; j < n ; ++j)
  55. #define MAX(a,b,c) max(a,max(b,c))
  56. #define ld long double
  57. typedef long long int ll;
  58.  
  59. const int oo = INT_MAX;
  60. const ll OO = 1e18;
  61.  
  62. using namespace std;
  63.  
  64. ll GCD(ll a, ll b) { return((!b) ? a : GCD(b, a % b)); }
  65. ll LCM(ll a, ll b) { return a / (GCD(a, b)) * b; }
  66. bool isPrime(ll n) {
  67. 	if (n == 2)re 1;
  68. 	if (n < 2 || n % 2 == 0)re 0;
  69. 	for (ll i = 3; i * i <= n; i += 2)
  70. 		if (n % i == 0)re 0;
  71. 	re 1;
  72. }
  73.  
  74. ll mod = 1000000000 + 7;
  75.  
  76. int arr[1003][1003];     // if 1 then it is road
  77. deque<pii> q;
  78. int x[] = { -1  ,1, 0, 0, -2, 2, 0, 0, -1, -2, -1, -2, 1, 2, 1, 2, -1, -1,-2,-2,1,1,2,2 };
  79. int y[] = { 0,0,-1,1,0,0,2,-2,-1,-1,-2,-2,-1,-1,-2,-2,1,2,1,2,1,2,1,2 };
  80. map<pii, int> dist;
  81.  
  82. int r, c, sr, sc, er, ec;
  83.  
  84. bool ok(int rr, int cc) {
  85.  
  86. 	if (rr < 0 || rr >= r || cc < 0 || cc >= c)
  87. 		re false;
  88. 	re true;
  89. }
  90.  
  91. int main() {
  92.  
  93. 	IO;
  94. 	/*freopen("gift1.in", "r", stdin);
  95. 	freopen("gift1.out", "w", stdout);*/
  96.  
  97. 	cin >> r >> c >> sr >> sc >> er >> ec;
  98. 	sr--; sc--; er--; ec--;
  99.  
  100. 	fri(0, r) {
  101. 		frj(0, c) {
  102. 			char ch;
  103. 			cin >> ch;
  104. 			if (ch == '.')
  105. 				arr[i][j] = 1;
  106. 			dist[mp(i, j)] = oo;
  107. 		}
  108. 	}
  109.  
  110. 	q.push_front(mp(sr, sc));
  111. 	dist[mp(sr, sc)] = 0;
  112.  
  113. 	while (!q.empty()) {
  114. 		pii p = q.front();
  115. 		q.pop_front();
  116. 		fri(0, 4) {
  117. 			int nx = p.first + x[i];
  118. 			int ny = p.second + y[i];
  119. 			if (dist[p] < dist[mp(nx, ny)] && ok(nx, ny) && arr[nx][ny]) {
  120. 				q.push_front(mp(nx, ny));
  121. 				dist[mp(nx, ny)] = dist[p];
  122. 			}
  123. 		}
  124.  
  125.  
  126. 		fri(4, 24) {
  127. 			int nx = p.first + x[i];
  128. 			int ny = p.second + y[i];
  129. 			if (dist[p] + 1 < dist[mp(nx, ny)] && ok(nx, ny) && arr[nx][ny]) {
  130. 				q.push_back(mp(nx, ny));
  131. 				dist[mp(nx, ny)] = dist[p] + 1;
  132. 			}
  133. 		}
  134.  
  135. 	}
  136.  
  137. 	if (dist[mp(er, ec)] == oo)
  138. 		cout << -1;
  139. 	else
  140. 		cout << dist[mp(er, ec)];
  141.  
  142. 	re 0;
  143. }
  144.  
  145.  
  146.  
Success #stdin #stdout 0s 4368KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/1LKnsI
language:
C++ (gcc 8.3)
created:
3 years ago
visibility:
secret

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!