fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int tran(int x1, int x2, int x3, int x4, int x5, int x6, int x7, int x8, int x9){
  4. 	return (((((((((x1 * 10 + x2) * 10 + x3) * 10 + x4) * 10 + x5) * 10 + x6) * 10 + x7) * 10 + x8) * 10 + x9));  
  5. } 
  6. int main(){
  7. 	int target = 123456789;  
  8. 	int first_grid = 0;
  9. 	int p = pow(10, 9);   
  10. 	for(int i = 1, num;i <= 9;i++){
  11. 		cin >> num;
  12. 		p /= 10; 
  13. 		first_grid += num * p; 
  14. 	} 
  15.  	queue<pair<int, int> > bfs;
  16. 	bfs.push({first_grid, 0});
  17. 	set<int> st; 
  18. 	st.insert(first_grid);  
  19.  
  20. 	if(first_grid == target){
  21. 		cout << 0 << endl;
  22. 		return 0;  
  23. 	} 
  24.  
  25. 	while(true){
  26. 		pair<int, int> a = bfs.front();
  27. 		bfs.pop();
  28. 		int grid = a.first;
  29. 		int dis = a.second;
  30. 		int x9 = grid % 10;
  31. 		grid /= 10; 
  32. 		int x8 = grid % 10;
  33. 		grid /= 10; 
  34. 		int x7 = grid % 10;
  35. 		grid /= 10; 
  36. 		int x6 = grid % 10;
  37. 		grid /= 10; 
  38. 		int x5 = grid % 10;
  39. 		grid /= 10; 
  40. 		int x4 = grid % 10;
  41. 		grid /= 10; 
  42. 		int x3 = grid % 10;
  43. 		grid /= 10; 
  44. 		int x2 = grid % 10;
  45. 		grid /= 10; 
  46. 		int x1 = grid % 10;
  47. 		vector<int> aa;
  48. 		aa.push_back(tran(x2, x1, x3, x4, x5, x6, x7, x8, x9));
  49. 		aa.push_back(tran(x1, x3, x2, x4, x5, x6, x7, x8, x9));
  50. 		aa.push_back(tran(x1, x2, x3, x5, x4, x6, x7, x8, x9));
  51. 		aa.push_back(tran(x1, x2, x3, x4, x6, x5, x7, x8, x9));
  52. 		aa.push_back(tran(x1, x2, x3, x4, x5, x6, x8, x7, x9));
  53. 		aa.push_back(tran(x1, x2, x3, x4, x5, x6, x7, x9, x8));
  54.  
  55. 		aa.push_back(tran(x4, x2, x3, x1, x5, x6, x7, x8, x9));
  56. 		aa.push_back(tran(x1, x5, x3, x4, x2, x6, x7, x8, x9));
  57. 		aa.push_back(tran(x1, x2, x6, x4, x5, x3, x7, x8, x9));
  58. 		aa.push_back(tran(x1, x2, x3, x7, x5, x6, x4, x8, x9));
  59. 		aa.push_back(tran(x1, x2, x3, x4, x8, x6, x7, x5, x9));
  60. 		aa.push_back(tran(x1, x2, x3, x4, x5, x9, x7, x8, x6));
  61.  
  62. 		for(int x : aa){
  63. 			if(x == target){
  64. 				cout << dis + 1 << endl;
  65. 				return 0;  
  66. 			} 
  67. 			int pre = st.size();
  68. 			st.insert(x);
  69. 			if(st.size() != pre){
  70. 				bfs.push({x, dis + 1});
  71. 				st.insert(x);  
  72. 			} 
  73. 		}   
  74. 	} 
  75. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
2 1 3
7 5 9
8 4 6
stdout
copy 
4
https://ideone.com/TA6ULw
language:
C++14 (gcc 8.3)
created:
1 day 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!