华容道动态规划

【华容道】华容道最优解，请将代码末的棋盘输入，程序会打印每一步走法。

#include #include #include #include #include #define Rep(i, x, y) for (int i = x; i <= y; i ++) #define Dwn(i, x, y) for (int i = x; i >= y; i --) #define RepE(i, x) for (int i = pos[x]; i; i = g[i].nex) #define v g[i].y #define col(x, y) map[x][y] #define Nexts sv = encode(map); if (find(sv, d + 1)) { ans[d] = s; return 1; } using namespace std; typedef long long ll; typedef double db; const int n = 5, m = 4; int px[14], py[14], l, lim = 1; int mx[4] = { 0, 1, 0, -1 }, my[4] = { 1, 0, -1, 0 }; ll ans[600]; map vis, step; ll encode(int map[n + 2][m + 2]) { int t1 = 3, t2 = 7; bool vd[14]; memset(vd, 0, sizeof(vd)); vd[0] = 1; Rep(i, 1, n) { Rep(j, 1, m) { int c; if (!vd[ c = map[i][j] ]) { if (c >= 7) px[t2] = i, py[t2] = j, t2 ++; else px[c] = i, py[c] = j; vd[c] = 1; } } } ll s = 0; Dwn(i, 10, 1) s = (s * 4 + py[i] - 1) * 5 + px[i] - 1; return s; } void decode(ll s, int map[n + 2][m + 2]) { Rep(i, 1, 10) px[i] = s % 5 + 1, s /= 5, py[i] = s % 4 + 1, s /= 4; Rep(i, 0, n + 1) Rep(j, 0, m + 1) map[i][j] = 0; Rep(i, 0, 1) Rep(j, 0, 1) map[ px[1] + i ][ py[1] + j ] = 1; Rep(i, 0, 1) map[ px[2] ][ py[2] + i ] = 2; Rep(k, 3, 6) Rep(i, 0, 1) map[ px[k] + i ][ py[k] ] = k; Rep(k, 7, 10) map[ px[k] ][ py[k] ] = k; } bool find(ll s, int d) { if (d > lim || step[s] && step[s] < d) return 0; if (vis[s] == lim) return 0; vis[s] = lim; step[s] = d; int map[n + 2][m + 2]; decode(s, map); int _x[3], _y[3], t = 0; Rep(i, 1, n) Rep(j, 1, m) if (!map[i][j]) _x[++ t] = i, _y[t] = j; if (map[5][2] == 1 && map[5][3] == 1) { printf("%d\n", d); ans[l = d] = s; return 1; } ll sv; Rep(i, 1, 2) { int x = _x[i], y = _y[i], c, x1, y1, x2, y2; Rep(j, 0, 3) { x1 = x + mx[j], y1 = y + my[j]; c = map[x1][y1]; x2 = x + mx[j] * 2, y2 = y + my[j] * 2; if (c >= 7) { map[x][y] = c, map[x1][y1] = 0; Nexts; map[x1][y1] = c; } else if (c > 1 && c == map[x2][y2]) { map[x][y] = c, map[x2][y2] = 0; Nexts; map[x2][y2] = c; } } map[x][y] = 0; } Rep(j, 0, 3) { int c1, c2, r; c1 = map[ _x[1] + mx[j] ][ _y[1] + my[j] ]; if (!c1) continue ; c2 = map[ _x[2] + mx[j] ][ _y[2] + my[j] ]; if (c1 == c2) { r = c1 == 1 ? 2 : 1; Rep(i, 1, 2) { map[ _x[i] ][ _y[i] ] = c1; map[ _x[i] + mx[j] * r ][ _y[i] + my[j] * r ] = 0; } Nexts; Rep(i, 1, 2) { map[ _x[i] ][ _y[i] ] = 0; map[ _x[i] + mx[j] * r ][ _y[i] + my[j] * r ] = c1; } } } return 0; } int main() { int t1 = 7, map[n + 2][m + 2]; Rep(i, 0, n + 1) Rep(j, 0, m + 1) map[i][j] = 0; char s[8]; Rep(i, 1, n) { gets (s + 1); Rep(j, 1, m) { if (s[j] == ' ') map[i][j] = 0; else map[i][j] = s[j] == '*' ? t1 ++ : s[j] - '0'; } } while (!find( encode(map), 1 )) { lim ++; if (lim > 200) { puts("no solution"); return 0 ; } } cout << l << endl; Rep(t, 1, l) { system("pause"); decode(ans[t], map); Rep(i, 1, n) { Rep(j, 1, m) { if (map[i][j] >= 7) printf("*"); else if (!map[i][j]) printf(" "); else printf("%d", map[i][j]); } puts(""); } } return 0; } /*3114 3114 5226 5**6 ***/

华容道

推荐阅读

硼肥对红薯有什么作用红薯硼肥使用

疏懒是什么意思愧赧是什么意思

俄暂停执行黑海港口农产品外运协议，马克龙称是“巨大错误”

米酒做法窍门视频米酒做法窍门

金铲铲之战龙什么效果金铲铲之战时空裂痕羁绊龙效果介绍

经期可以喝减肥咖啡吗

你就是一个正在发生的故事……

黄油保存温度是多少

胶带剩下的胶怎么擦掉怎么擦干净胶带留下的胶

007大破量子危机结局前男友怎么找到的,007大破量子危机的故事梗概

北京最低工资标准1540 北京最低工资标准提至1720元

靓汤是什么意思

电吉他扫拨怎样消音？有哪些适合在家用的电吉他音响？

与其锦上添花不如雪中送炭的意思与其锦上添花不如雪中送炭的意思最佳答案

当你拥抱生命时，生活的美便向你走来

驾驶证扣留期间可以开车吗

鑫龙凤珠宝质量怎么样

怯懦怎么读怯懦释义

蜥蜴和壁虎的区别蜥蜴和壁虎有什么区别

对手机|“网购手机”和“实体店买手机”有什么区别？可算是知道了