fork download
copy 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 1e18;  
  10.  
  11. // Coi mỗi trạng thái bảng là một đỉnh trong đồ thị, còn thao tác biến đổi bảng chính là cạnh
  12. // Ta sẽ hash bảng sang một số ở hệ 9 (các chữ số có giá trị từ 0 -> 8)
  13. int pow9[10]; 
  14.  
  15. void precompute() {
  16. 	pow9[0] = 1; 
  17. 	for (int i = 1; i <= 9; i++) pow9[i] = pow9[i - 1] * 9; 
  18. }
  19.  
  20. // Hoán đổi chữ số ở vị trí i và j của u cho nhau
  21. int swap(int u, int i, int j) {
  22. 	int digit_i = u / pow9[i] % 9;  
  23. 	int digit_j = u / pow9[j] % 9; 
  24. 	int v = u - pow9[i] * digit_i - pow9[j] * digit_j; 
  25. 	v += pow9[i] * digit_j + pow9[j] * digit_i;  
  26. 	return v; 
  27. }
  28.  
  29. // Ta sẽ chỉ xét thao tác swap ô (x, y) với ô nằm bên phải và ô nằm phía dưới nó
  30. // Giả sử ô (x, y) (toạ độ 2D) tương ứng với vị trí i (toạ độ 1D)
  31. // Thì ô (x, y + 1) sẽ tương ứng với vị trí i + 1 (i % 3 != 2 hay tồn tại ô (x, y + 1))
  32. //     ô (x + 1, y) sẽ tương ứng với vị trí i + 3 (i + 3 < 9 hay tồn tại ô (x + 1, y))
  33. void bfs(int s, int t) {
  34. 	vector<bool> vis(pow9[9], false); 
  35. 	queue<ii> q; 
  36. 	vis[s] = true;  
  37. 	q.push({s, 0});   
  38.  
  39. 	while (!q.empty()) {
  40. 		ii front = q.front(); q.pop();  
  41. 		int u = front.first, d = front.second;  
  42.  
  43. 		if (u == t) {
  44. 			cout << d << '\n'; 
  45. 			break; 
  46. 		}
  47.  
  48. 		for (int i = 0; i < 9; i++) {
  49. 			if (i % 3 != 2) {
  50. 				int v = swap(u, i, i + 1); 
  51. 				if (!vis[v]) {
  52. 					vis[v] = true; 
  53. 					q.push({v, d + 1}); 
  54. 				}
  55. 			}
  56. 			if (i + 3 < 9) {
  57. 				int v = swap(u, i, i + 3); 
  58. 				if (!vis[v]) {
  59. 					vis[v] = true; 
  60. 					q.push({v, d + 1}); 
  61. 				}
  62. 			}
  63. 		}
  64. 	}
  65. } // O(9! * 9 * 2)
  66.  
  67. int main() {
  68. 	ios::sync_with_stdio(false); 
  69. 	cin.tie(nullptr); 	
  70. 	precompute();  
  71.  
  72. 	int s = 0;   
  73. 	for (int i = 0; i < 9; i++) {
  74. 		int num; cin >> num;   
  75. 		--num; 
  76. 		s += pow9[i] * num;  
  77. 	}
  78.  
  79. 	int t = 0;  
  80. 	for (int i = 0; i < 9; i++) {
  81. 		t += pow9[i] * i;  
  82. 	}
  83.  
  84. 	bfs(s, t);  
  85. }
Success #stdin #stdout 0.01s 50548KB
comments (?)
stdin
copy 
2 1 3
7 5 9
8 4 6
stdout
copy 
4
https://ideone.com/sXHqCN
language:
C++14 (gcc 8.3)
created:
291 days 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!