fork(1) download
copy 
  1. #include <iostream>
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. pair<long long int,long long int> check(pair<int,int>v,int first,int second)
  5. {
  6. 	if(v.first+first>=1&&v.first+first<=8)
  7. 	{
  8. 		if(v.second+second>=1&&v.second+second<=8)
  9. 		{
  10. 			//cout<<v.first<<v.second;
  11. 			v.first = v.first+first;
  12. 			v.second = v.second+second;
  13. 		//	cout<<v.first<<v.second<<first<<second<<" ";
  14. 			return v;
  15. 		}
  16. 	}
  17. 	v.first=(-1);
  18. 	v.second=(-1);
  19. 	return v;
  20. }
  21.  
  22. int main() {
  23. 	ios_base::sync_with_stdio;
  24. 	cin.tie(0);
  25. 	long long int t;
  26. 	cin>>t;
  27. 	while(t--)
  28. 	{
  29. 		string str1,str2;
  30. 		cin>>str1>>str2;
  31. 		pair<int,int>p1,p2;
  32. 		p1 = make_pair((str1[0]-'a'+1),str1[1]-'0');
  33. 		p2 = make_pair((str2[0]-'a'+1),str2[1]-'0');
  34. 		queue<pair<long long int,long long int>>q;
  35. 		q.push(p1);
  36. 		map<pair<long long int,long long int>,long long int>dist;
  37. 		map<pair<long long int,long long int>,bool>visited;
  38. 		for(int i=1;i<=9;i++)
  39. 		for(int j=1;j<=9;j++)
  40. 		{
  41. 			dist[make_pair(i,j)]=(-1);
  42. 			visited[make_pair(i,j)]=false;
  43. 		}
  44. 		visited[p1] = true;
  45. 		dist[p1] = 0;
  46. 		while(!q.empty())
  47. 		{
  48. 			//cout<<q.size()<<" ";
  49. 			pair<int,int>p = q.front();
  50. 			q.pop();
  51. 			//cout<<p.first<<p.second<<" ";
  52. 			pair<long long int,long long int> ans;
  53. 			ans = check(p,2,1);
  54. 			if(ans.first!=(-1)&&ans.second!=(-1)&&visited[ans]==false)
  55. 			{
  56. 				//cout<<1<<" ";
  57. 				visited[ans]=true;
  58. 				dist[ans] = dist[p] + 1;
  59. 				q.push(ans);
  60. 			}
  61. 			ans = check(p,2,-1);
  62. 			if(ans.first!=(-1)&&ans.second!=(-1)&&visited[ans]==false)
  63. 			{
  64. 				visited[ans]=true;
  65. 				dist[ans] = dist[p] + 1;
  66. 				q.push(ans);
  67. 			}
  68. 			ans = check(p,-2,1);
  69. 			if(ans.first!=(-1)&&ans.second!=(-1)&&visited[ans]==false)
  70. 			{
  71. 				visited[ans]=true;
  72. 				dist[ans] = dist[p] + 1;
  73. 				q.push(ans);
  74. 			}
  75. 			ans = check(p,-2,-1);
  76. 			if(ans.first!=(-1)&&ans.second!=(-1)&&visited[ans]==false)
  77. 			{
  78. 				visited[ans]=true;
  79. 				dist[ans] = dist[p] + 1;
  80. 				q.push(ans);
  81. 			}
  82. 			ans = check(p,1,2);
  83. 			if(ans.first!=(-1)&&ans.second!=(-1)&&visited[ans]==false)
  84. 			{
  85. 				visited[ans]=true;
  86. 				dist[ans] = dist[p] + 1;
  87. 				q.push(ans);
  88. 			}
  89. 			ans = check(p,-1,2);
  90. 			if(ans.first!=(-1)&&ans.second!=(-1)&&visited[ans]==false)
  91. 			{
  92. 				visited[ans]=true;
  93. 				dist[ans] = dist[p] + 1;
  94. 				q.push(ans);
  95. 			}
  96. 			ans = check(p,1,-2);
  97. 			if(ans.first!=(-1)&&ans.second!=(-1)&&visited[ans]==false)
  98. 			{
  99. 				visited[ans]=true;
  100. 				dist[ans] = dist[p] + 1;
  101. 				q.push(ans);
  102. 			}
  103. 			ans = check(p,-1,-2);
  104. 			if(ans.first!=(-1)&&ans.second!=(-1)&&visited[ans]==false)
  105. 			{
  106. 				visited[ans]=true;
  107. 				dist[ans] = dist[p] + 1;
  108. 				q.push(ans);
  109. 			}
  110. 		}
  111. 		cout<<dist[p2]<<endl;
  112. 	}
  113. 	// your code goes here
  114. 	return 0;
  115. }
Success #stdin #stdout 0s 4404KB
comments (?)
stdin
copy 
1
h8 a1
stdout
copy 
6
https://ideone.com/u6AeVx
language:
C++14 (gcc 8.3)
created:
6 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!