fork(1) download 
  1.  
  2. #include<iostream>
  3. #include<set>
  4. #include<cstdio>
  5. #include<cstdlib>
  6. using namespace std;
  7. const int size = 10;//game size
  8. const int times = 9;
  9. const int partyN = 18;
  10. //time , size
  11. int partyBoard[times][size][2] = { 0 };//0 is empty
  12. bool usedParty[times][partyN+1];//1~18, party in this time
  13. bool playedGame[partyN+1][size];//has this party played this game?
  14. set< pair<int, int>  > vs;//party vs party
  15.  
  16. void init()
  17. {
  18.  
  19. 	for (int i = 0; i < times; i++)
  20. 	{
  21. 		for (int j = 0; j < size; j++)
  22. 		{
  23. 			partyBoard[i][j][0] = 0;
  24. 			partyBoard[i][j][1] = 0;
  25. 		}
  26. 		for (int j = 0; j < partyN+1; j++)
  27. 		{
  28. 			usedParty[i][j] = false;
  29. 			playedGame[j][i] = false;
  30. 		}
  31. 	}
  32. }
  33.  
  34.  
  35. void show()
  36. {
  37.  
  38. 	for (int i = 0; i < times; i++)
  39. 	{
  40. 		for (int j = 0; j < size; j++)
  41. 		{
  42. 			if (i != 1)
  43. 				printf(" ");
  44.  
  45. 			printf("(%2d,%2d) ", partyBoard[i][j][0], partyBoard[i][j][1]);
  46.  
  47. 		}
  48. 		printf("\n");
  49. 	}
  50. }
  51.  
  52. //x is game
  53. //y is time
  54. bool backTrack(int x, int y, int r)
  55. {	
  56. //	show();
  57. 	if (x == size)
  58. 	{
  59. 		if (r==0)
  60. 			return backTrack(0, y + 1, partyN);
  61. 		else
  62. 			return false;
  63. 	}
  64. 	if (y == times)
  65. 	{
  66. 		return true;
  67. 	}
  68.  
  69.  
  70. 	for (int i = 1; i < partyN + 1; i++)
  71. 	for (int j = i + 1; j < partyN + 1; j++)
  72. 	{
  73. 		if (usedParty[y][i] == false && usedParty[y][j] == false)//time, party
  74. 		if (playedGame[i][x] == false && playedGame[j][x] == false)//party, game
  75. 		if (vs.count(make_pair(i,j))==0)
  76. 		{
  77.  
  78.  
  79. 			//push
  80. 			partyBoard[y][x][0] = i;
  81. 			partyBoard[y][x][1] = j;
  82. 			usedParty[y][i] = true;
  83. 			usedParty[y][j] = true;
  84. 			playedGame[i][x] = true;
  85. 			playedGame[j][x] = true;
  86. 			vs.insert(make_pair(i, j));
  87.  
  88. 			if (backTrack(x+1,y,r-2))
  89. 			{
  90. 				return true;
  91. 			}
  92.  
  93. 			//pop
  94. 			partyBoard[y][x][0] = 0;
  95. 			partyBoard[y][x][1] = 0;
  96. 			usedParty[y][i] = false;
  97. 			usedParty[y][j] = false;
  98. 			playedGame[i][x] = false;
  99. 			playedGame[j][x] = false;
  100. 			vs.erase(make_pair(i, j));
  101. 		}
  102. 	}
  103.  
  104. 	//skip game
  105. 	if (size-1-x>=r/2)
  106. 	if (backTrack(x+1,y,r))
  107. 		return true;
  108.  
  109. 	return false;
  110. }
  111.  
  112.  
  113.  
  114. int main(int argc, char* argv[])
  115. {
  116.  
  117. 	cout << backTrack(0, 0, 18) << endl;
  118.  
  119. 	show();
  120. 	return 0;
  121. }
  122.  
  123.  
Success #stdin #stdout 3.8s 3232KB
comments (?)
stdin 
zero
stdout 
1
 ( 1, 2)  ( 3, 4)  ( 5, 6)  ( 7, 8)  ( 9,10)  (11,12)  (13,14)  (15,16)  (17,18)  ( 0, 0) 
( 3, 5) ( 1, 6) ( 2, 4) ( 9,11) ( 7,12) ( 8,10) (15,17) (13,18) (14,16) ( 0, 0) 
 ( 4, 6)  ( 2, 5)  ( 1, 3)  (10,12)  ( 8,11)  ( 7, 9)  (16,18)  (14,17)  (13,15)  ( 0, 0) 
 ( 7,10)  ( 8, 9)  (11,13)  ( 1, 4)  ( 2,14)  (15,18)  ( 3, 6)  ( 5,12)  ( 0, 0)  (16,17) 
 ( 8,12)  ( 7,11)  ( 9,14)  ( 2,15)  ( 1,16)  (13,17)  ( 4, 5)  ( 3,10)  ( 0, 0)  ( 6,18) 
 ( 9,13)  (10,14)  ( 7,15)  ( 3,17)  ( 4,18)  ( 2,16)  ( 1, 8)  ( 0, 0)  ( 6,12)  ( 5,11) 
 (11,17)  ( 0, 0)  ( 8,18)  ( 5,16)  ( 3,13)  ( 4,14)  ( 9,12)  ( 2, 6)  ( 1, 7)  (10,15) 
 (14,15)  (12,18)  (10,16)  ( 6,13)  ( 5,17)  ( 0, 0)  ( 2, 7)  ( 1, 9)  ( 3,11)  ( 4, 8) 
 ( 0, 0)  (13,16)  (12,17)  (14,18)  ( 6,15)  ( 1, 5)  (10,11)  ( 4, 7)  ( 2, 8)  ( 3, 9)
https://ideone.com/PCzfZn
language:
C++ (gcc 8.3)
created:
8 years 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!