首页 > 代码库 > POJ 1077 A*
POJ 1077 A*
链接：
http://poj.org/problem?id=1077
题意：
经典8数码问题，直接暴力bfs也能做，但是一定要先hash一下
题解：
这里的估价函数为当前状态下，所有的数字与其位置的之差的绝对值总和
话说我又被c++的string坑惨了
代码：
31 int vis[MAXN]; 32 int fac[] = { 1,1,2,6,24,120,720,5040,40320,362880 }; 33 34 int find(char s[]) {//康托展开 35 int res = 0; 36 bool has[10] = { 0 }; 37 rep(i, 0, 9) { 38 int x = s[i] - ‘0‘, y = 0; 39 rep(j, 1, x) if (!has[j]) y++; 40 res += y*fac[8 - i]; 41 has[x] = 1; 42 } 43 return res; 44 } 45 46 int get_h(const char s[]) { 47 int res = 0; 48 rep(i, 0, 9) res += abs(s[i] - ‘1‘ - i); 49 return res; 50 } 51 52 struct Node { 53 char s[15]; 54 int g; 55 Node(char s[], int g) :g(g) { strcpy(this->s, s); } 56 const bool operator<(const Node &t) const { 57 return g + get_h(s) > t.g + get_h(t.s); 58 } 59 }; 60 61 priority_queue<Node> que; 62 63 int main() { 64 char s[15]; 65 rep(i, 0, 9) { 66 string t; 67 cin >> t; 68 if (t[0] == ‘x‘) s[i] = ‘9‘; 69 else s[i] = t[0]; 70 } 71 vis[find(s)] = 100; 72 que.push(Node(s, 0)); 73 while (!que.empty()) { 74 Node pre = que.top(); que.pop(); 75 int x = 0; 76 while (pre.s[x] != ‘9‘) x++; 77 if (x >= 3) { 78 char ss[15]; 79 strcpy(ss, pre.s); 80 ss[x] = ss[x - 3]; 81 ss[x - 3] = ‘9‘; 82 if (!vis[find(ss)]) { 83 vis[find(ss)] = -3; 84 que.push(Node(ss, pre.g + 1)); 85 } 86 } 87 if (x < 6) { 88 char ss[15]; 89 strcpy(ss, pre.s); 90 ss[x] = ss[x + 3]; 91 ss[x + 3] = ‘9‘; 92 if (!vis[find(ss)]) { 93 vis[find(ss)] = 3; 94 que.push(Node(ss, pre.g + 1)); 95 } 96 } 97 if (x % 3) { 98 char ss[15]; 99 strcpy(ss, pre.s);100 ss[x] = ss[x - 1];101 ss[x - 1] = ‘9‘;102 if (!vis[find(ss)]) {103 vis[find(ss)] = -1;104 que.push(Node(ss, pre.g + 1));105 }106 }107 if (x % 3 != 2) {108 char ss[15];109 strcpy(ss, pre.s);110 ss[x] = ss[x + 1];111 ss[x + 1] = ‘9‘;112 if (!vis[find(ss)]) {113 vis[find(ss)] = 1;114 que.push(Node(ss, pre.g + 1));115 }116 }117 if (vis[0]) break;118 }119 if (!vis[0]) return puts("unsolvable"), 0;120 int y = 0;121 char ss[15] = "123456789";122 string ans;123 while (vis[y] != 100) {124 int x = 0;125 while (ss[x] != ‘9‘) x++;126 switch (vis[y]) {127 case -3: {128 ss[x] = ss[x + 3];129 ss[x + 3] = ‘9‘;130 ans += ‘u‘;131 break;132 }133 case 3: {134 ss[x] = ss[x - 3];135 ss[x - 3] = ‘9‘;136 ans += ‘d‘;137 break;138 }139 140 case -1: {141 ss[x] = ss[x + 1];142 ss[x + 1] = ‘9‘;143 ans += ‘l‘;144 break;145 }146 case 1: {147 ss[x] = ss[x - 1];148 ss[x - 1] = ‘9‘;149 ans += ‘r‘;150 break;151 }152 }153 y = find(ss);154 }155 reverse(all(ans));156 cout << ans << endl;157 return 0;158 }
POJ 1077 A*
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。