puzzle（1115）移箱迷宫、星云穿越

目录移箱迷宫初级策略一纵向匹配法策略二横向匹配法策略三基于移动方格的方案简化递归搜索策略四难以分割的相邻同色块中级星云穿越两对残局三对残局1号2号3号4号5号6号7号8号9号10号11号12号13号14号15号16号简单4对中级6对高级7对困难8对移箱迷宫规则补充规则每次滑动相当于是盒子和四邻居之一交换位置这个邻居可能是空格也可能是盒子交换位置之后所有格子往下掉落。如果形成3个以上也会一次性全部消除。如果多个方向同时形成3个或以上也会一次性全部消除。消除之后剩下的盒子会往下掉落如果形成新的可消除组合则自动继续消除。初级11首先寻找匹配方向然后寻找优先消除块最后找到操作方法15首先寻找匹配方向然后寻找优先消除块我画了3个黑框因为左边2个块和上边1个块距离太远所以在消除这3个块之前还要先把右边的6个块消除掉。最后找到操作方法23这里的匹配结果是蓝色格子往左移2步所以操作方法就是24273033394042首先红色和深蓝色的水平坐标是OK的即只要往下掉到同一行即可消除而黄色是左边的格子需要往右移动一步。基于此比较容易想到一个三步的操作方法根据这个方案可以想到一个步骤更少的方案45参考下文《递归搜索》49策略一纵向匹配法首先寻找匹配方向然后寻找优先消除块最后找到操作方法。参考初级关卡11和15策略二横向匹配法如果寻找到的匹配方向是把某个单个的箱子横着移动则直接得到对应数量的操作内容。参考初级关卡23策略三基于移动方格的方案简化有时我们拿到一个操作数比较多的方案可以分析我们的整体操作是把哪些方格移动了移到了什么位置基于这个操作结果可以反推出一个操作数更少的操作方案。参考初级关卡42递归搜索我们把不同的颜色用正整数区分0表示空格然后用递归搜索即可搜出一个解。注意我们在框定尺寸时要往左右两边留出空列而最上面是不需要留出空行的。代码bool down(vectorvectorintv) { bool flag false; int row v.size(), col v[0].size(); for (int j 0; j col; j) { int low 0; for (int i 1; i row; i) { if (v[low][j] 0) { if (v[i][j])low i; } else { if (v[i][j])continue; for (int k i; klow; k--) { v[k][j] v[k - 1][j]; } v[low][j] 0; flag true; low; } } } return flag; } bool dels(vectorvectorint v) { int row v.size(), col v[0].size(); vectorvectorboolcanDel(row, vectorbool(col, false)); for (int i 0; i row; i) { for (int j 2; j col; j) { if (v[i][j] v[i][j - 2] v[i][j] v[i][j - 1] v[i][j]) { canDel[i][j - 2] canDel[i][j - 1] canDel[i][j] true; } } } for (int i 2; i row; i) { for (int j 0; j col; j) { if (v[i][j] v[i-2][j] v[i][j] v[i-1][j] v[i][j]) { canDel[i-2][j] canDel[i-1][j] canDel[i][j] true; } } } bool flag false; for (int i 0; i row; i) { for (int j 0; j col; j) { if (canDel[i][j]) { flag true, v[i][j] 0; } } } return flag; } void downAndDel(vectorvectorint v) { while (down(v) || dels(v)); } bool isFinish(const vectorvectorint v) { int row v.size(), col v[0].size(); for (int i 0; i row; i) { for (int j 0; j col; j) { if (v[i][j]) return false; } } return true; } bool search(vectorvectorint v, int n) { if (!n)return isFinish(v); int row v.size(), col v[0].size(); for (int i 0; i row; i) { for (int j 1; j col; j) { if (v[i][j] v[i][j - 1])continue; auto v2 v; v[i][j] ^ v[i][j - 1] ^ v[i][j] ^ v[i][j - 1]; downAndDel(v); if (search(v, n-1)) { cout i j i j - 1 endl; return true; } v v2; } } for (int i 1; i row; i) { for (int j 0; j col; j) { if (v[i][j] v[i-1][j])continue; auto v2 v; v[i][j] ^ v[i - 1][j] ^ v[i][j] ^ v[i - 1][j]; downAndDel(v); if (search(v, n - 1)) { cout i j i-1 j endl; return true; } v v2; } } return false; }以初级关卡45为例所以调用代码就是int main() { vectorvectorintv{ {0,1,0,0,0,0}, {0,2,0,0,0,0}, {0,3,0,0,0,0}, {0,2,1,0,0,0}, {0,1,3,3,0,0}, {0,2,2,1,0,0}, {0,1,1,2,2,0} }; search(v, 2); return 0; }运行结果4 1 4 03 1 2 1从下往上先把3,1和2,1互换再把4,1和4,0互换即策略四难以分割的相邻同色块在上面的初级关卡45中其实很容易想到红色的块往左推的操作但是如果第一步就这样操作就会造成四个黄色块最下面一行2个倒数第二行2个一起消除从而无解。我的思路一直是如何分割倒数第二行的2个黄色块一直没想过可以让这6个黄色块同时消除。所以策略四就是如果遇到难以分割的相邻同色块考虑不分割而是两组同时消除。中级2这一关的关键是4个黄的要一起消除4个深蓝的也要一起消除。星云穿越最强大脑同款项目。两对残局三对残局1号2步转化成2号2号2步转化成3号3号4号2步就全挨着了5号1步就全挨着了6号2步变成7号7号2步把不挨着的左下和右上消了剩下2对挨着的8号2步就全挨着了9号2步就全挨着了10号3步左上左变成11号11号1步就全挨着了12号2步变成13号13号2步变成14号14号2步把橙色的第一列和最后一列消掉15号2步变成16号16号1步就全挨着了简单4对中级6对高级7对困难8对