Chương trình đếm số từ có thể tạo từ ma trận chữ cái 4x4 trong Python

Cho bàn cờ 4x4 chữ cái và danh sách từ. Tìm số từ lớn nhất có thể tạo được bằng chuỗi ký tự liền kề (8 hướng), mỗi ô dùng tối đa 1 lần/một từ (có thể dùng lại cho từ khác).

Ví dụ ma trận 4x4, từ ["bat", "far", "mat"] → 3 (tất cả đều tạo được).

Giải thuật (Trie + DFS Backtracking)

1. Xây Trie từ danh sách từ, nút cuối đánh dấu '*': True.
2. DFS từ mỗi ô: nếu ký tự ở nút Trie, đệ quy 8 hướng. Đánh dấu ô đã dùng tạm thời (gán '#').
3. Gặp nút có '*': tăng đếm, xóa '*' (tránh đếm trùng từ).

Ví dụ minh họa

class Solution:
    def solve(self, A, words):
        N, M = len(A), len(A[0])
        trie = {}
        for word in words:
            node = trie
            for c in word:
                node = node.setdefault(c, {})
            node['*'] = True
        
        ans = 0
        def dfs(x, y, node):
            nonlocal ans
            if '*' in node:
                del node['*']
                ans += 1
            temp = A[x][y]
            A[x][y] = '#'
            for dx in (-1, 0, 1):
                for dy in (-1, 0, 1):
                    if dx == 0 and dy == 0:
                        continue
                    nx, ny = x + dx, y + dy
                    if 0 <= nx < N and 0 <= ny < M and A[nx][ny] in node:
                        dfs(nx, ny, node[A[nx][ny]])
            A[x][y] = temp
        
        for i in range(N):
            for j in range(M):
                if A[i][j] in trie:
                    dfs(i, j, trie[A[i][j]])
        return ans

ob = Solution()
matrix = [["m","b","f","d"],["x","a","y","a"],["t","z","t","r"],["s","q","q","q"]]
words = ["bat", "far", "mat"]
print(ob.solve(matrix, words))  # Output: 3

Đầu vào / Đầu ra

Input: ma trận 4x4, ["bat", "far", "mat"]

Output: 3