fork(4) download
copy 
  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <iostream>
  5. #include <sstream>
  6. #include <utility>
  7. #include <string>
  8. #include <cstring>
  9. #include <set>
  10. #include <queue>
  11. #include <stack>
  12. #include <cmath>
  13. #include <map>
  14. #include <bitset>
  15. using namespace std;
  16.  
  17. int ch1();
  18. void ch2(int);
  19. void shift_down(int);
  20. void shift_left(int);
  21. vector <int> v(9),v1(9);
  22.  
  23. int main()
  24. {
  25.     map <int,int> mp;
  26.     vector <string> res;
  27. 	vector <int> num;
  28. 	queue <int> qu;
  29. 	string  str,str1;
  30. 	string st[6]={"1H","2H","3H","1V","2V","3V"};
  31.  
  32. 	int goal=123456789;
  33. 	int t1,t2,t3;
  34.  
  35. 	mp[goal]=0;
  36. 	qu.push(0); 
  37. 	num.push_back(goal);
  38. 	res.push_back("");
  39. 	t3=1;
  40. 	while(!qu.empty())
  41. 	{
  42. 		t1=qu.front(); qu.pop();
  43. 		ch2(num[t1]);
  44. 		//horizontal 
  45. 		for(int i=0;i<3;i++)
  46. 		{
  47. 			v1=v;
  48. 			shift_left(i);
  49. 			t2=ch1();
  50. 			if(mp.find(t2)==mp.end())
  51. 			{
  52.  
  53. 				mp[t2]=t3;
  54. 				qu.push(t3); t3++;
  55. 				num.push_back(t2);
  56. 				str=res[t1]+st[i];
  57. 				res.push_back(str);
  58. 			}
  59. 		}
  60. 		//vertical
  61. 		for(int i=0;i<3;i++)
  62. 		{
  63. 			v1=v;
  64. 			shift_down(i);
  65. 			t2=ch1();
  66. 			if(mp.find(t2)==mp.end())
  67. 			{
  68.  
  69. 				mp[t2]=t3;
  70. 				qu.push(t3); t3++;
  71. 				num.push_back(t2);
  72. 				str=res[t1]+st[i+3];
  73. 				res.push_back(str);
  74. 			}
  75. 		}
  76. 	}
  77.  
  78.  
  79. 	while(scanf("%d",&v1[0]))
  80. 	{
  81. 		if(v1[0]==0) break;
  82. 		for(int i=1;i<9;i++) scanf("%d",&v1[i]);
  83.  
  84. 		t1=ch1();
  85.  
  86. 		if(mp.find(t1)==mp.end()) printf("Not solvable\n");
  87. 		else 
  88. 		{
  89. 			t1=mp[t1];
  90. 			printf("%d ",res[t1].length()/2);
  91. 			for(int i=res[t1].length();i>=0;i--) printf("%c",res[t1][i]);
  92. 			printf("\n");
  93. 		}
  94. 	}
  95.  
  96. 	return 0;
  97. }
  98.  
  99.  
  100. int ch1()
  101. {
  102. 	int ans=0;
  103. 	for(int i=0;i<9;i++) {ans*=10; ans+=v1[i];}
  104. 	return ans;
  105. }
  106.  
  107. void ch2(int x)
  108. {
  109. 	for(int i=8;i>=0;i--) {v[i]=x%10; x=x/10;}
  110. }
  111.  
  112. void shift_down(int x)
  113. {
  114. 	swap(v1[x],v1[x+6]); swap(v1[x+3],v1[x+6]);
  115. }
  116.  
  117. void shift_left(int x)
  118. {
  119.     x=x*3;
  120. 	swap(v1[x],v1[x+2]); swap(v1[x+1],v1[x]);
  121. }
Success #stdin #stdout 0.71s 17248KB
comments (?)
stdin
copy 
2 3 1
4 5 6
7 8 9

7 3 9
2 5 1
4 8 6

1 2 3
4 5 6
7 9 8

3 7 2 
1 5 6
4 8 9

3 2 1
4 5 6
7 8 9

2 3 1
5 6 4
8 9 7

2 3 7
5 6 1
8 9 4

3 7 2
5 6 1
8 9 4

3 7 2
1 5 6
8 9 4
0
stdout
copy 
1 H1
3 V3V1H1
Not solvable
3 H1H1V1
Not solvable
3 H3H2H1
4 V3H3H2H1
5 H1V3H3H2H1
4 H3H1H1V1
https://ideone.com/6RT3AS
11513 - 9 Puzzle
language:
C++ (gcc 8.3)
created:
10 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!