fork(2) download
copy 
  1. #include <iostream>
  2. #include <math.h>
  3. #include <stdio.h>
  4. #include <map>
  5. #include <queue>
  6. using namespace std;
  7.  
  8. const long long x_max = 100000;
  9. const long long y_max = 100000;
  10. #define ll long long
  11.  
  12. int inSide (ll x, ll y)
  13. {
  14. 	if (x>=-x_max && x<=x_max && y>=-y_max && y<=y_max)
  15. 		return 1;
  16. 	return 0;
  17. }
  18.  
  19. ll vertex (ll x, ll y)
  20. {
  21. 	return (2*y_max*y_max + 3*y_max - x_max + 1) + (2*y_max + 1)*y + x;
  22. }
  23.  
  24. ll x_t, y_t;
  25. ll n;
  26. ll x_i, y_i;
  27. map <ll, char> prevent;
  28. void read ()
  29. {
  30. 	scanf ("%lld%lld", &x_t, &y_t);
  31. 	scanf ("%lld", &n);
  32. 	for (ll i=0; i<n; i++)
  33. 	{
  34. 		scanf ("%lld%lld", &x_i, &y_i);
  35. 		prevent[vertex(x_i, y_i)] = 'X';
  36. 	}
  37. }
  38.  
  39. map <ll, char> check;
  40. map <ll, ll> len;
  41. void init ()
  42. {
  43. 	prevent.clear();
  44. 	check.clear();
  45. 	len.clear();
  46. }
  47.  
  48. struct data
  49. {
  50. 	ll x, y;
  51. 	data (ll x_, ll y_)
  52. 	{
  53. 		x = x_;
  54. 		y = y_;
  55. 	}
  56. };
  57.  
  58. ll x_xq[] = {-1, -2, -2, -1, +1, +2, +2, +1};
  59. ll y_xq[] = {-2, -1, +1, +2, +2, +1, -1, -2};
  60.  
  61. void BFS (ll x, ll y)
  62. {
  63. 	queue <data> q;
  64. 	q.push(data(x, y));
  65. 	check[vertex(x, y)] = 'Y';
  66. 	len[vertex(x, y)] = 0;
  67.  
  68. 	while (!q.empty())
  69. 	{
  70. 		data v = q.front();
  71. 		q.pop();
  72. 		for (int i=0; i<8; i++)
  73. 		{
  74. 			ll x_p = v.x+x_xq[i];
  75. 			ll y_p = v.y+y_xq[i];
  76. 			if (inSide(x_p, y_p)==1 && check[vertex(x_p, y_p)]!='Y' && prevent[vertex(x_p, y_p)]!='X')
  77. 			{
  78. 				q.push(data(x_p, y_p));
  79. 				len[vertex(x_p, y_p)] = len[vertex(v.x, v.y)]+1;
  80. 				check[vertex(x_p, y_p)] = 'Y';
  81. 				if (x_p == x_t && y_p == y_t) return;
  82. 			}
  83. 		}
  84. 	}
  85. }
  86.  
  87. int main ()
  88. {
  89. 	int t;
  90. 	scanf ("%d", &t);
  91. 	while (1)
  92. 	{
  93. 		if (t==0) break;
  94. 		t--;
  95. 		init();
  96. 		read();
  97. 		BFS(0, 0);
  98. 		printf("%lld\n", len[vertex(x_t, y_t)]);
  99. 	}
  100. 	return 0;
  101. }
Success #stdin #stdout 0s 4516KB
comments (?)
stdin
copy 
1
2 4
0
stdout
copy 
2
https://ideone.com/HY9CiO
o- PTIT017K - ACM PTIT 2017 K - QUÂN MÃ
language:
C++ (gcc 8.3)
created:
7 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!