fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. unordered_set<string> visited;
  5.  
  6. // Defined globally to be used in process_swap
  7. queue<pair<string, int>> q;
  8. int moves;
  9. string curboard;
  10.  
  11. // Processing swapping the numbers in x, y positions
  12. void process_swap(int x, int y) {
  13. 	swap(curboard[x], curboard[y]);
  14. 	// Check whether already visited this potential board
  15. 	if (visited.find(curboard) == visited.end()) {
  16. 		q.push({curboard, moves + 1});
  17. 		visited.insert(curboard);
  18. 	}
  19. 	// Restore to original board
  20. 	swap(curboard[x], curboard[y]);
  21. }
  22.  
  23. int main() {
  24. 	string inp;
  25. 	// Rewriting the input as a string
  26. 	for (int i = 0; i < 9; i++) {
  27. 		int a;
  28. 		cin >> a;
  29. 		inp += to_string(a - 1);
  30. 	}
  31.  
  32. 	q.push({inp, 0});
  33. 	while (!q.empty()) {
  34. 		tie(curboard, moves) = q.front();
  35. 		q.pop();
  36. 		if (curboard == "012345678") {
  37. 			cout << moves << endl;
  38. 			return 0;
  39. 		}
  40.  
  41. 		// Horizontal swaps
  42. 		for (int i = 0; i < 9; i += 3) {
  43. 			process_swap(i, i + 1);
  44. 			process_swap(i + 1, i + 2);
  45. 		}
  46. 		// Vertical swaps
  47. 		for (int i = 0; i < 3; i++) {
  48. 			process_swap(i, i + 3);
  49. 			process_swap(i + 3, i + 6);
  50. 		}
  51. 	}
  52. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/3TBB8n
language:
C++14 (gcc 8.3)
created:
1 day 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!