fork(2) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. long long myhash( const string & key )
  5. {
  6. 	long long hash = 0;
  7.     for(char c : key) {
  8.     	c -= 'a';
  9.     	hash = (hash<<4) | (long long)c;
  10.     }
  11.     return hash;
  12. }
  13.  
  14. void put(long long& hash, int i, long long c) {
  15. 	long long mask4 = (1LL<<4) - 1;
  16. 	hash = (hash & (~(mask4<<(4*i)))) ^ (c<<(4*i));
  17. }
  18.  
  19. void swap(long long& hash, int i, int j) {
  20. 	long long icode = (hash >> (4*i)) & ((1LL<<4)-1);
  21. 	long long jcode = (hash >> (4*j)) & ((1LL<<4)-1);
  22. 	put(hash, i, jcode);
  23. 	put(hash, j, icode);
  24. }
  25.  
  26. // unordered_map<string, int, decltype(&myhash)> vis[] = {
  27. // 	unordered_map<string, int, decltype(&myhash)>(0, myhash),
  28. // 	unordered_map<string, int, decltype(&myhash)>(0, myhash)
  29. // };
  30.  
  31. unordered_map<long long, int> vis[2];
  32.  
  33.  
  34. int find(int id, long long xx, long long yy, int maxdepth) {
  35. 	queue<pair<long long, int>> q;
  36. 	q.push({xx, 0});
  37. 	vis[id][xx] = 0;
  38. 	int result = 123;
  39. 	while(q.size()) {
  40. 		auto cur = q.front(); q.pop();
  41. 		//if(cur.second <= 2) cout << cur.first << " " << cur.second << endl;
  42. 		if(id == 0 && cur.first == yy) {
  43. 			return cur.second;
  44. 		}
  45. 		if(cur.second == 4) return result;
  46. 		if(id == 1 && vis[1-id].count(cur.first)) {
  47. 			return cur.second + vis[1-id][cur.first];
  48. 		}
  49. 		for(int i = 0; i < 10; i++) {
  50. 			long long t = cur.first;
  51. 			for(int len = 3; i+len/2 < 10 && i-len/2 >= 0; len += 2) {
  52. 				swap(t, i-len/2, i+len/2);
  53. 				if(!vis[id].count(t)) {
  54. 					if(id == 1 && vis[1-id].count(t)) {
  55. 						return cur.second + 1 + vis[1-id][t];
  56. 					}
  57. 					if(cur.second+1 < maxdepth) q.push({t, cur.second+1});
  58. 					vis[id][t] = cur.second+1;
  59. 				}
  60. 			}
  61. 			t = cur.first;
  62. 			for(int len = 2; i+len/2 < 10 && i-len/2+1 >= 0; len += 2) {
  63. 				swap(t, i-len/2+1, i+len/2);
  64. 				if(!vis[id].count(t)) {
  65. 					if(id == 1 && vis[1-id].count(t)) {
  66. 						return cur.second + 1 + vis[1-id][t];
  67. 					}
  68. 					if(cur.second+1 < maxdepth) q.push({t, cur.second+1});
  69. 					vis[id][t] = cur.second+1;
  70. 				}
  71. 			}	
  72. 		}
  73. 	}
  74. 	return result;
  75. }
  76.  
  77. int main() {
  78. 	ios_base::sync_with_stdio(0);
  79. 	string s, e;
  80. 	vis[0].max_load_factor(0.25);
  81. 	vis[1].max_load_factor(0.25);
  82. 	while(true) {
  83. 		cin >> s >> e;
  84. 		vis[0].clear();
  85. 		vis[1].clear();
  86. 		if (s == "*") break;
  87. 		find(0, myhash(s), myhash(e), 4);
  88. 		cout << min(9, find(1, myhash(e), myhash(s), 4)) << "\n";
  89. 	}
  90.  
  91. 	return 0;
  92. }
Success #stdin #stdout 0.19s 23296KB
comments (?)
stdin
copy 
abcdefghij jahbgcfedi
abcdefghij jahbgcidef
abcdefghij jabcdefghi
abcdefghij abedcfghij
* *
stdout
copy 
6
6
2
1
https://ideone.com/n5Y1Aj
language:
C++14 (gcc 8.3)
created:
5 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!