字节机考-4-10-第四题

# coding=utf-8
import sys
 
def f2(a, types):
    n = len(a)
    max_card = -1
    for i in range(len(a)): # 这里可以优化
        node = [int(e) for e in str(a[i])]
        max_card = max(max_card, max(node))
        node = set(node)
        t = 0
        for e in node:
            e = int(e)
            t += ((2**(e)))
        a[i] = t
    b = [bin(i)[2:] for i in a] 
    if max_card < types:
        return -1
    max_len = [len(b_node) for b_node in b] 
    size = 2 ** max(max_len) 
 
    dp = [[float('inf') for i in range(size)]  for _ in range(n)]
    item0 = a[0]
    for j in range(size):
        dp[0][j] = 1 if j == item0 else float('inf')
    for i in range(n):
            dp[i][0] = 0
 
    for i in range(1,n):
        item = a[i]
        for j in range(size):
            new_j = j | item
 
            dp[i][new_j] = min(dp[i][new_j], dp[i-1][j]+1, dp[i][new_j])
            dp[i][j] = min(dp[i-1][j], dp[i][j])
 
    return dp[-1][-2]
 
t = input()
for i in range(t):
    mnk = sys.stdin.readline().split()
    n,m,k = int(mnk[0]), int(mnk[1]), int(mnk[2])
    items = []
    for nn in range(n):
        cards = sys.stdin.readline().split()
        items.append(int("".join(cards)))
    print(f2(items, m))