讨论/技术交流/讨论最强大脑第 8 季 第一题的编程实现/
讨论最强大脑第 8 季 第一题的编程实现

没人回复啊,换个分区发一下,欢迎讨论。

题目描述

这是最强大脑第八季第一题的描述,如果实在没看懂,大家可以看一下节目。
其实就是用透明色块拼图,色块可以翻转(两面都是可用的)。

back.png

Snipaste_2021-01-17_17-39-45.png


题目转化

乍一看,好像没办法用代码解决问题,不知道怎么抽象,下面将拼好的图给大家看一下,应该就有思路了。

Snipaste_2021-01-19_14-36-56.png

可以看出其实每个拼图图块仍然是以方块为基础的,只不过四条边分别被替换成为阶梯边 0,S 边 1,波浪边 2 和 ⚡ 边 3。所以可以转化为如下题目:

从最上方边的最左侧开始顺时针输入拼图边框 [2,1,0,1,2,3,0,2,3,1,3,0][2,1,0,1,2,3,0,2,3,1,3,0]

输入 nn 块拼图碎片(边顺时针)

[[2,0,1,0],[1,2,3,0],[0,1,3,2],[1,0,2,3],[3,2,1,0],[3,2,1,2],[2,0,3,1],[1,2,2,0],[1,3,0,2]][[2,0,1,0],[1,2,3,0],[0,1,3,2],[1,0,2,3],[3,2,1,0],[3,2,1,2],[2,0,3,1],[1,2,2,0],[1,3,0,2]]

求拼图的解决方案数。

抛砖引玉

可能这不是最好的问题转化方式,基于这种方式,可以使用回溯法解决问题,其实也就是暴力,每个碎块每个位置无非就是两个面四个角度8种使用方式,暴力的话复杂度就是 9!89!*8
但是如果问题规模扩大呢,比如拼图宽度变为 10,边的种类暂且不变仍然是4,n = 10 X 10 = 100,O(n!)O(n!) 的时间复杂度显然不切实际,大家有没有什么好的解决方案呢?欢迎讨论,如本文有错误,欢迎指正。

11
共 3 个回复

就想图片像素那样,0表示白色,1表示黑色。

呃,抽象成 0,1的像素会不会更好?