列表

详情

LCP 58. 积木拼接

欢迎各位勇者来到力扣城，本次试炼主题为「积木拼接」。 勇者面前有 6 片积木（厚度均为 1），每片积木的形状记录于二维字符串数组 shapes 中，shapes[i] 表示第 i 片积木，其中 1 表示积木对应位置无空缺，0 表示积木对应位置有空缺。 例如 ["010","111","010"] 对应积木形状为 image.png

拼接积木的规则如下：

例如 3*3、4*4 的积木片的中心点如图所示（红色点）： middle_img_v2_c2d91eb5-9beb-4c06-9726-f7dae149d86g.png{:height="150px"}

请返回这 6 片积木能否拼接成一个严丝合缝的正方体且每片积木正好对应正方体的一个面。

注意：

示例 1：

输入：shapes = [["000","110","000"],["110","011","000"],["110","011","110"],["000","010","111"],["011","111","011"],["011","010","000"]]

输出：true

解释： cube.gif

示例 2：

输入：shapes = [["101","111","000"],["000","010","111"],["010","011","000"],["010","111","010"],["101","111","010"],["000","010","011"]]

输出：false

解释： 由于每片积木片的中心点在拼接时必须处于正方体对应面的中心点，积木片 ["010","011","000"] 不能作为 ["100","110","000"] 使用，因此无法构成正方体

提示：

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution { public: bool composeCube(vector<vector<string>>& shapes) { } };

python3 解法, 执行用时: 900 ms, 内存消耗: 23.5 MB, 提交时间: 2023-09-05 07:48:47 

class Solution:
    def composeCube(self, shapes: List[List[str]]) -> bool:
        def cal(shape):
            res = [0]*48
            for i, j in product(range(n), range(n)):
                if shape[i][j] == '0':
                    continue
                for turn, (i2, j2) in enumerate([(i, j), (i, n-1-j)]):
                    for rotate, (x, y) in enumerate([(i2, j2), (j2, n-1-i2), (n-1-i2, n-1-j2), (n-1-j2, i2)]):
                        for side, (x2, y2, z2) in enumerate([(x, y, 0), (x, y, n-1), (0, y, x), (n-1, y, x), (x, 0, y), (x, n-1, y)]):
                            res[turn*24+rotate*6+side] |= 1<<(x2*n*n+y2*n+z2)
            return res
    
        n = len(shapes[0])
        if sum(''.join(shape).count('1') for shape in shapes) != 2*n*n+4*(n-1)*(n-2):
            return False
        dp = {0}
        for i in range(6):
            dp = {st|st2 for st in cal(shapes[i]) for st2 in dp if not st&st2}
        return bool(dp)

golang 解法, 执行用时: 0 ms, 内存消耗: 2.6 MB, 提交时间: 2023-09-05 07:47:59 

// 每条边压缩成二进制
func encode(a [][]byte) (res [4][2]int) {
	n := len(a)
	for i, b := range a[0] {
		res[0][0] |= int(b&1) << i // 正向
		res[0][1] |= int(b&1) << (n - 1 - i) // 反向
		res[2][0] |= int(a[n-1][i]&1) << i
		res[2][1] |= int(a[n-1][i]&1) << (n - 1 - i)
	}
	for i, r := range a {
		res[1][0] |= int(r[n-1]&1) << i
		res[1][1] |= int(r[n-1]&1) << (n - 1 - i)
		res[3][0] |= int(r[0]&1) << i
		res[3][1] |= int(r[0]&1) << (n - 1 - i)
	}
	return
}

// 顺时针旋转矩阵 90°
func rotate(a [][]byte) [][]byte {
	n, m := len(a), len(a[0])
	b := make([][]byte, m)
	for i := range b {
		b[i] = make([]byte, n)
	}
	for i, r := range a {
		for j, v := range r {
			b[j][n-1-i] = v
		}
	}
	return b
}

func composeCube(shapes [][]string) bool {
	n := len(shapes[0])
	a := [6][8][4][2]int{} // [积木][旋转+翻转][边][0-正向/1-反向]
	for i, shape := range shapes {
		t := make([][]byte, n)
		for j, s := range shape {
			t[j] = []byte(s)
		}
		for j := 0; j < 4; j++ {
			a[i][j] = encode(t)
			t = rotate(t)
		}
		for _, r := range t {
			for j := 0; j < n/2; j++ {
				r[j], r[n-1-j] = r[n-1-j], r[j]
			}
		}
		for j := 4; j < 8; j++ {
			a[i][j] = encode(t)
			t = rotate(t)
		}
	}

	// 判断两条边是否恰好重叠（除了顶角）
	MASK := 1<<(n-1) - 2
	ok := func(v, w int) bool { return v&w == 0 && (v|w)&MASK == MASK }

	type pair struct{ who, rot int }
	fill := [6]pair{} // 枚举每个积木以什么旋转/翻转姿势放在哪个面（0-顶面，1234-侧面，5-底面）
	vis := 0
	var dfs func(int) bool
	dfs = func(p int) bool { // 当前考虑的面
		if p == 6 { return true }
		for cur := 1; cur < 6; cur++ { // 枚举 6 个积木（固定第一个积木放在顶面）
			if vis>>cur&1 > 0 { continue }
			vis ^= 1 << cur
			for rot := 0; rot < 8; rot++ { // 枚举 8 种旋转+翻转的情况
				switch p {
				case 1:
					// 1 和 0 是否有冲突
					if !ok(a[cur][rot][0][0], a[0][0][2][0]) {
						continue
					}
				case 2:
					// 2 和 0 1 是否有冲突
					w, r := fill[p-1].who, fill[p-1].rot
					if !ok(a[cur][rot][0][0], a[0][0][1][1]) || // 边是否冲突
						!ok(a[cur][rot][3][0], a[w][r][1][0]) ||
						a[0][0][2][1]&1 == 0 && a[cur][rot][0][0]&1 == 0 && a[w][r][0][1]&1 == 0 { // 角是否冲突
						continue
					}
				case 3:
					// 3 和 0 2 是否有冲突
					w, r := fill[p-1].who, fill[p-1].rot
					if !ok(a[cur][rot][0][0], a[0][0][0][1]) ||
						!ok(a[cur][rot][3][0], a[w][r][1][0]) ||
						a[0][0][1][0]&1 == 0 && a[cur][rot][0][0]&1 == 0 && a[w][r][0][1]&1 == 0 {
						continue
					}
				case 4:
					// 4 和 0 1 3 是否有冲突
					w, r := fill[p-1].who, fill[p-1].rot
					w1, r1 := fill[1].who, fill[1].rot
					if !ok(a[cur][rot][0][0], a[0][0][3][0]) ||
						!ok(a[cur][rot][3][0], a[w][r][1][0]) ||
						!ok(a[cur][rot][1][0], a[w1][r1][3][0]) ||
						a[0][0][3][0]&1 == 0 && a[cur][rot][0][0]&1 == 0 && a[w][r][0][1]&1 == 0 ||
						a[0][0][2][0]&1 == 0 && a[cur][rot][0][1]&1 == 0 && a[w1][r1][0][0]&1 == 0 {
						continue
					}
				default:
					// 5 和 1 2 3 4 是否有冲突
					w1, r1 := fill[1].who, fill[1].rot
					w2, r2 := fill[2].who, fill[2].rot
					w3, r3 := fill[3].who, fill[3].rot
					w4, r4 := fill[4].who, fill[4].rot
					if !ok(a[cur][rot][0][0], a[w1][r1][2][0]) ||
						!ok(a[cur][rot][1][0], a[w2][r2][2][0]) ||
						!ok(a[cur][rot][2][1], a[w3][r3][2][0]) ||
						!ok(a[cur][rot][3][1], a[w4][r4][2][0]) ||
						a[cur][rot][0][1]&1 == 0 && a[w1][r1][2][1]&1 == 0 && a[w2][r2][2][0]&1 == 0 ||
						a[cur][rot][1][1]&1 == 0 && a[w2][r2][2][1]&1 == 0 && a[w3][r3][2][0]&1 == 0 ||
						a[cur][rot][2][0]&1 == 0 && a[w3][r3][2][1]&1 == 0 && a[w4][r4][2][0]&1 == 0 ||
						a[cur][rot][0][0]&1 == 0 && a[w4][r4][2][1]&1 == 0 && a[w1][r1][2][0]&1 == 0 {
						continue
					}
				}
				fill[p] = pair{cur, rot}
				if dfs(p + 1) { return true }
			}
			vis ^= 1 << cur
		}
		return false
	}
	return dfs(1)
}

cpp 解法, 执行用时: 1360 ms, 内存消耗: 7.4 MB, 提交时间: 2023-09-05 07:47:33 

class Solution {
    int n;
    vector<vector<string>> shapes;
    // 整个立方体有哪些位置被占用了
    bool A[10][10][10];
    // 哪些面被占用了
    short used[6];

    // 每个面的起始位置
    int CUBE_BASE[6][3] = {
        0, 0, 0,
        0, 0, 1,
        1, 0, 1,
        0, 0, 1,
        0, 0, 1,
        0, 1, 1
    };
    // 每个面 xyz 的增加“方向”
    int CUBE_DIR[6][6] = {
        1, 0, 0, 0, 1, 0,
        1, 0, 0, 0, 1, 0,
        0, 0, -1, 0, 1, 0,
        0, 0, -1, 0, 1, 0,
        0, 0, -1, 1, 0, 0,
        0, 0, -1, 1, 0, 0
    };

    // 形状旋转后的起始位置
    int SHAPE_BASE[4][2] = {0, 0, 0, 1, 1, 0, 1, 1};
    // 形状旋转后行和列的增加“方向”
    int SHAPE_DIR[4][2] = {1, 1, 1, -1, -1, 1, -1, -1};

    // x：哪个形状
    // k：哪个面
    // s：哪种旋转
    // rc：行列是否交换
    // modify：0 = 检查是否占用；1 = 占用；-1 = 取消占用
    bool gao(int x, int k, int s, bool rc, int modify) {
        for (int a = 0; a < n; a++) for (int b = 0; b < n; b++) {
            int i = CUBE_BASE[k][0] * (n - 1) + CUBE_DIR[k][0] * a + CUBE_DIR[k][3] * b;
            int j = CUBE_BASE[k][1] * (n - 1) + CUBE_DIR[k][1] * a + CUBE_DIR[k][4] * b;
            int z = CUBE_BASE[k][2] * (n - 1) + CUBE_DIR[k][2] * a + CUBE_DIR[k][5] * b;
            int si = SHAPE_BASE[s][0] * (n - 1) + SHAPE_DIR[s][0] * (rc ? b : a);
            int sj = SHAPE_BASE[s][1] * (n - 1) + SHAPE_DIR[s][1] * (rc ? a : b);
            if (shapes[x][si][sj] == '1') {
                if (modify == 1) A[i][j][z] = true;
                else if (modify == -1) A[i][j][z] = false;
                else if (A[i][j][z]) return false;
            }
        }
        return true;
    }

    bool dfs(int x) {
        if (x == 6) return true;
        for (int k = 0; k < 6; k++) if (!used[k]) {
            for (int i = 0; i < 4; i++) for (int j = 0; j <= 1; j++) {
                if (!gao(x, k, i, j, 0)) continue;
                gao(x, k, i, j, 1);
                used[k] = true;
                if (dfs(x + 1)) return true;
                used[k] = false;
                gao(x, k, i, j, -1);
            }
        }
        return false;
    }

public:
    bool composeCube(vector<vector<string>>& shapes) {
        n = shapes[0].size();
        int expected = n * n * n - (n - 2) * (n - 2) * (n - 2);
        int actual = 0;
        for (auto &shape : shapes) for (auto &line : shape) for (char c : line) actual += c - '0';
        if (expected != actual) return false;
        this->shapes = shapes;
        return dfs(0);
    }
};

上一题

© 2024 leetcode.cn