puzzle（1123）星系探秘

目录一规则二策略三实战1简单2中等3困难4专家四计算机求解1暴力求解2DFS剪枝1求出所有可选的目标位置2求出绿色球每列刚好一个的所有情况3依次检查所有情况最强大脑《Q星探秘》同款puzzle一规则参考Q星探秘二策略策略一寻找突破口。根据最终状态每一个扇区都得是一个三角形。而每一个绿色和蓝色的点只能待在本扇区或移动到相邻扇区。所以一开始的突破口就是寻找一整个扇区都没有绿色和蓝色点的扇区。策略二只操作确定的点。尽量全程只操作确定的点对于有两种情况需要选择的尽量留到后半程去选择。策略三优先合成能合成三角形的优先合成三角形。从第1个三角形开始连续往外扩张。三实战1简单2中等3困难4专家四计算机求解以专家级为例这是上面的实战示例。1暴力求解时间复杂度4^722DFS剪枝1求出所有可选的目标位置int row 8; int col 24; struct Points { int r; int c; bool operator(const Points p) const { if (c p.c)return r p.r; return c p.c; } }; enum COLOR { GREEN, BLUE, RED }; vectorPoints getNext(Points p, COLOR c) { vectorPointsans; ans.push_back(p); if (c GREEN) { ans.push_back({ p.r,(p.c 1) % col }); ans.push_back({ p.r,(p.c col - 1) % col }); if (p.r)ans.push_back({ p.r - 1,p.c }); if (p.r row - 1)ans.push_back({ p.r 1,p.c }); } if (c BLUE) { if (p.r) { ans.push_back({ p.r - 1,(p.c col - 1) % col }); ans.push_back({ p.r - 1,(p.c 1) % col }); } if (p.r row - 1) { ans.push_back({ p.r 1,(p.c col - 1) % col }); ans.push_back({ p.r 1,(p.c 1) % col }); } } if (c RED) { ans.push_back({ p.r,(p.c 2) % col }); ans.push_back({ p.r,(p.c col - 2) % col }); if (p.r 2)ans.push_back({ p.r - 2,p.c }); if (p.r row - 2)ans.push_back({ p.r 2,p.c }); } return ans; } setPoints getTarget(vectorPointsgreen, vectorPointsblue, vectorPointsred) { mapPoints, intm1, m2, m3; for (auto p : green) { for (auto pi : getNext(p, GREEN))m1[pi]; } for (auto p : blue) { for (auto pi : getNext(p, BLUE))m2[pi]; } for (auto p : red) { for (auto pi : getNext(p, RED))m3[pi]; } setPointsans; for (auto pair : m1) { if (m2[pair.first] m3[pair.first])ans.insert(pair.first); } return ans; } int main() { vectorPointsgreen{ {1,0},{3,1},{3,2},{4,2},{0,4},{3,5},{3,6},{3,7},{7,8},{6,9},{3,11},{4,11}, {0,12},{7,12},{0,13},{1,15},{3,16},{5,17},{5,18},{6,18},{6,19},{0,20},{6,21},{4,23} }; vectorPointsblue{ {2,2},{4,3},{5,4},{0,5},{2,5},{4,5},{2,6},{7,7},{6,8},{3,10},{6,10},{1,12},{4,12}, {1,13},{1,14},{5,16},{3,17},{6,17},{7,19},{1,20},{4,20},{5,21},{0,22},{3,23} }; vectorPointsred{ {2,0},{3,0},{4,1},{5,1},{3,4},{1,6},{6,6},{1,7},{2,7},{7,9},{4,10},{5,10}, {7,11},{2,14},{4,14},{0,15},{6,15},{2,17},{7,18},{3,19},{6,20},{1,21},{2,21},{6,22} }; cout green.size() blue.size() red.size() endl; setPoints target getTarget(green, blue, red); cout target.size(); return 0; }输出24 24 2438因为24*8个格子里面只有38个格子是可选的目标位置所以以这个作为剪枝的基础能极大提高效率。2求出绿色球每列刚好一个的所有情况void dfs(vectorPointsv, COLOR c, setPoints target, vectorboolused, int id, vectorPointsans, setsetPoints allAns) { if (id col) { setPoints target; for (auto p : ans)target.insert(p); allAns.insert(target); return; } Points p v[id]; for (auto pi : getNext(p, c)) { if (used[pi.c])continue; if (target.find(pi) target.end())continue; ans.push_back(pi); used[pi.c] true; dfs(v, c, target, used, id 1, ans, allAns); used[pi.c] false; ans.erase(ans.begin() (ans.size() - 1)); } } //求出绿色球每列刚好一个的所有情况 setsetPoints solveGreen(vectorPointsgreen, setPoints target) { setsetPointsallAns; vectorboolused(col, false); vectorPointsans; dfs(green, GREEN, target, used, 0, ans, allAns); return allAns; } int main() { vectorPointsgreen{ {1,0},{3,1},{3,2},{4,2},{0,4},{3,5},{3,6},{3,7},{7,8},{6,9},{3,11},{4,11}, {0,12},{7,12},{0,13},{1,15},{3,16},{5,17},{5,18},{6,18},{6,19},{0,20},{6,21},{4,23} }; vectorPointsblue{ {2,2},{4,3},{5,4},{0,5},{2,5},{4,5},{2,6},{7,7},{6,8},{3,10},{6,10},{1,12},{4,12}, {1,13},{1,14},{5,16},{3,17},{6,17},{7,19},{1,20},{4,20},{5,21},{0,22},{3,23} }; vectorPointsred{ {2,0},{3,0},{4,1},{5,1},{3,4},{1,6},{6,6},{1,7},{2,7},{7,9},{4,10},{5,10}, {7,11},{2,14},{4,14},{0,15},{6,15},{2,17},{7,18},{3,19},{6,20},{1,21},{2,21},{6,22} }; setPoints target getTarget(green, blue, red); setsetPoints v solveGreen(green, target); cout v.size() endl; return 0; }输出963依次检查所有情况bool check(setPointstargetAns, vectorPointsv, COLOR c) { setsetPointsallAns; vectorboolused(col, false); vectorPointsans; dfs(v, c, targetAns, used, 0, ans, allAns); return allAns.find(targetAns)! allAns.end(); } int main() { vectorPointsgreen{ {1,0},{3,1},{3,2},{4,2},{0,4},{3,5},{3,6},{3,7},{7,8},{6,9},{3,11},{4,11}, {0,12},{7,12},{0,13},{1,15},{3,16},{5,17},{5,18},{6,18},{6,19},{0,20},{6,21},{4,23} }; vectorPointsblue{ {2,2},{4,3},{5,4},{0,5},{2,5},{4,5},{2,6},{7,7},{6,8},{3,10},{6,10},{1,12},{4,12}, {1,13},{1,14},{5,16},{3,17},{6,17},{7,19},{1,20},{4,20},{5,21},{0,22},{3,23} }; vectorPointsred{ {2,0},{3,0},{4,1},{5,1},{3,4},{1,6},{6,6},{1,7},{2,7},{7,9},{4,10},{5,10}, {7,11},{2,14},{4,14},{0,15},{6,15},{2,17},{7,18},{3,19},{6,20},{1,21},{2,21},{6,22} }; setPoints target getTarget(green, blue, red); setsetPoints v solveGreen(green, target); for (auto vi : v) { if (check(vi, blue, BLUE) check(vi, red, RED)) { for (auto p : vi)cout p.r p.c ; cout endl endl; } } return 0; }输出4 0 3 1 3 2 4 3 1 4 2 5 3 6 3 7 6 8 5 9 3 10 7 11 4 12 0 13 0 14 2 15 4 16 6 17 5 18 5 19 6 20 0 21 6 22 1 234 0 3 1 3 2 4 3 1 4 2 5 3 6 3 7 6 8 5 9 3 10 7 11 4 12 0 13 0 14 2 15 4 16 6 17 7 18 5 19 6 20 0 21 6 22 1 234 0 3 1 3 2 4 3 1 4 2 5 3 6 3 7 6 8 7 9 3 10 7 11 4 12 0 13 0 14 2 15 4 16 6 17 5 18 5 19 6 20 0 21 6 22 1 234 0 3 1 3 2 4 3 1 4 2 5 3 6 3 7 6 8 7 9 3 10 7 11 4 12 0 13 0 14 2 15 4 16 6 17 7 18 5 19 6 20 0 21 6 22 1 23也就是说一共有4种答案其实也就是第9列有2种情况第18列也有2种情况。实战中我自己推理出的答案对应的就是4 0 3 1 3 2 4 3 1 4 2 5 3 6 3 7 6 8 7 9 3 10 7 11 4 12 0 13 0 14 2 15 4 16 6 17 5 18 5 19 6 20 0 21 6 22 1 23这一组