fork download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <queue>
  4. #include <map>
  5. #define mp make_pair
  6. #define ii pair<int,int>
  7. using namespace std;
  8. const int maxn = 40000;
  9. const int oo = 1000000000;
  10. int t,a,b,c;
  11. map <ii,int> d;
  12. queue <ii> q;
  13. int bfs()
  14. {
  15. 	if (a+b<c) return -1;
  16. 	while (!q.empty())
  17. 	{
  18. 		ii p=q.front();
  19. 		q.pop();
  20. 		int x=p.first;
  21. 		int y=p.second;
  22. 		int dis=d[mp(x,y)];
  23. 		if ((x==c) or (y==c)) return dis;
  24. 		// do nuoc vao binh
  25. 		if (d.count(mp(a,y))==0)
  26. 		{
  27. 			q.push(mp(a,y));
  28. 			d[mp(a,y)]=dis+1;
  29. 		}
  30. 		if (d.count(mp(x,b))==0)
  31. 		{
  32. 			q.push(mp(x,b));
  33. 			d[mp(x,b)]=dis+1;
  34. 		}
  35. 		// do nuoc ra ngoai
  36. 		if (d.count(mp(x,0))==0) 
  37. 		{
  38. 			q.push(mp(x,0));
  39. 			d[mp(x,0)]=dis+1;
  40. 		}
  41. 		if (d.count(mp(0,y))==0)
  42. 		{
  43. 			q.push(mp(0,y));
  44. 			d[mp(0,y)]=dis+1;
  45. 		}
  46. 		// do nuoc tu binh b vao binh a
  47. 		if ((x+y<=a) and (d.count(mp(x+y,0))==0))
  48. 		{
  49. 			q.push(mp(x+y,0));
  50. 			d[mp(x+y,0)]=dis+1;
  51. 		}
  52. 		if ((x+y>a) and (d.count(mp(a,y-(a-x)))==0))
  53. 		{
  54. 			q.push(mp(a,y-(a-x)));
  55. 			d[mp(a,y-(a-x))]=dis+1;
  56. 		}
  57. 		// do nuoc tu binh b vao binh a
  58. 		if ((x+y<=b) and (d.count(mp(0,x+y))==0))
  59. 		{
  60. 			q.push(mp(0,x+y));
  61. 			d[mp(0,x+y)]=dis+1;
  62. 		}
  63. 		if ((x+y>b) and (d.count(mp(x-(b-y),b))==0))
  64. 		{
  65. 			q.push(mp(x-(b-y),b));
  66. 			d[mp(x-(b-y),b)]=dis+1;
  67. 		}
  68. 	}
  69. 	return -1;
  70. }
  71. void solve()
  72. {
  73. 	cin >> a >> b >> c;
  74. 	d.clear();
  75. 	while (!q.empty()) q.pop();
  76. 	q.push(mp(0,0));
  77. 	d[mp(0,0)]=0;
  78. 	cout << bfs() << '\n';
  79. }
  80. int main()
  81. {
  82. 	ios_base::sync_with_stdio(false);
  83. 	//freopen("POUR1.INP","r",stdin);
  84. 	cin >> t;
  85. 	for (int i=1; i<=t; i++)
  86. 	solve();
  87. 	return 0;
  88. }
Success #stdin #stdout 0s 3464KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/enJVFv
language:
C++14 (gcc 8.3)
created:
8 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!