from itertools import product
def count_safe_cells(matrix):
n = len(matrix)
m = len(matrix[0])
# 定義方向映射
directions = {
'U': (-1, 0),
'D': (1, 0),
'L': (0, -1),
'R': (0, 1)
}
def in_bounds(x, y):
"""檢查是否在邊界內"""
return 0 <= x < n and 0 <= y < m
# 計算給定矩陣的安全格子數量
def calculate_safe_cells(matrix):
graph = {}
for i in range(n):
for j in range(m):
graph[(i, j)] = []
if matrix[i][j] in directions:
dx, dy = directions[matrix[i][j]]
ni, nj = i + dx, j + dy
if in_bounds(ni, nj):
graph[(i, j)].append((ni, nj))
visited = set()
safe = set()
def dfs(node, path):
"""深度優先搜索來檢測環並計算安全格子"""
if node in visited:
if node in path:
# 發現環,將環內的節點加入安全集合
cycle_start = path.index(node)
for cyclic_node in path[cycle_start:]:
safe.add(cyclic_node)
return
visited.add(node)
path.append(node)
for neighbor in graph[node]:
dfs(neighbor, path)
path.pop()
for i in range(n):
for j in range(m):
if (i, j) not in visited:
dfs((i, j), [])
return len(safe)
# 找到所有 `?` 的位置
question_positions = [(i, j) for i in range(n) for j in range(m) if matrix[i][j] == '?']
max_safe_cells = 0
# 枚舉所有可能的方向分配
for replacements in product("UDLR", repeat=len(question_positions)):
# 替換 `?` 為特定方向
new_matrix = [list(row) for row in matrix]
for (i, j), direction in zip(question_positions, replacements):
new_matrix[i][j] = direction
max_safe_cells = max(max_safe_cells, calculate_safe_cells(new_matrix))
return max_safe_cells
# 多筆測試資料輸入處理
def process_test_cases(test_cases):
results = []
for case in test_cases:
results.append(count_safe_cells(case))
return results
# 測試案例
t = int(input("請輸入測試資料數量: "))
test_cases = []
for _ in range(t):
n, m = map(int, input("請輸入矩陣大小 n m: ").split())
matrix = [input("請輸入矩陣第 {} 行: ".format(i + 1)) for i in range(n)]
test_cases.append(matrix)
# 處理並輸出結果
results = process_test_cases(test_cases)
for idx, result in enumerate(results):
print(f"測資 {idx + 1} 的安全格子數量為: {result}")
ZnJvbSBpdGVydG9vbHMgaW1wb3J0IHByb2R1Y3QKCmRlZiBjb3VudF9zYWZlX2NlbGxzKG1hdHJpeCk6CiAgICBuID0gbGVuKG1hdHJpeCkKICAgIG0gPSBsZW4obWF0cml4WzBdKQogICAgCiAgICAjIOWumue+qeaWueWQkeaYoOWwhAogICAgZGlyZWN0aW9ucyA9IHsKICAgICAgICAnVSc6ICgtMSwgMCksCiAgICAgICAgJ0QnOiAoMSwgMCksCiAgICAgICAgJ0wnOiAoMCwgLTEpLAogICAgICAgICdSJzogKDAsIDEpCiAgICB9CiAgICAKICAgIGRlZiBpbl9ib3VuZHMoeCwgeSk6CiAgICAgICAgIiIi5qqi5p+l5piv5ZCm5Zyo6YKK55WM5YWnIiIiCiAgICAgICAgcmV0dXJuIDAgPD0geCA8IG4gYW5kIDAgPD0geSA8IG0KICAgIAogICAgIyDoqIjnrpfntablrprnn6npmaPnmoTlronlhajmoLzlrZDmlbjph48KICAgIGRlZiBjYWxjdWxhdGVfc2FmZV9jZWxscyhtYXRyaXgpOgogICAgICAgIGdyYXBoID0ge30KICAgICAgICBmb3IgaSBpbiByYW5nZShuKToKICAgICAgICAgICAgZm9yIGogaW4gcmFuZ2UobSk6CiAgICAgICAgICAgICAgICBncmFwaFsoaSwgaildID0gW10KICAgICAgICAgICAgICAgIGlmIG1hdHJpeFtpXVtqXSBpbiBkaXJlY3Rpb25zOgogICAgICAgICAgICAgICAgICAgIGR4LCBkeSA9IGRpcmVjdGlvbnNbbWF0cml4W2ldW2pdXQogICAgICAgICAgICAgICAgICAgIG5pLCBuaiA9IGkgKyBkeCwgaiArIGR5CiAgICAgICAgICAgICAgICAgICAgaWYgaW5fYm91bmRzKG5pLCBuaik6CiAgICAgICAgICAgICAgICAgICAgICAgIGdyYXBoWyhpLCBqKV0uYXBwZW5kKChuaSwgbmopKQogICAgICAgIAogICAgICAgIHZpc2l0ZWQgPSBzZXQoKQogICAgICAgIHNhZmUgPSBzZXQoKQoKICAgICAgICBkZWYgZGZzKG5vZGUsIHBhdGgpOgogICAgICAgICAgICAiIiLmt7HluqblhKrlhYjmkJzntKLkvobmqqLmuKznkrDkuKboqIjnrpflronlhajmoLzlrZAiIiIKICAgICAgICAgICAgaWYgbm9kZSBpbiB2aXNpdGVkOgogICAgICAgICAgICAgICAgaWYgbm9kZSBpbiBwYXRoOgogICAgICAgICAgICAgICAgICAgICMg55m854++55Kw77yM5bCH55Kw5YWn55qE56+A6bue5Yqg5YWl5a6J5YWo6ZuG5ZCICiAgICAgICAgICAgICAgICAgICAgY3ljbGVfc3RhcnQgPSBwYXRoLmluZGV4KG5vZGUpCiAgICAgICAgICAgICAgICAgICAgZm9yIGN5Y2xpY19ub2RlIGluIHBhdGhbY3ljbGVfc3RhcnQ6XToKICAgICAgICAgICAgICAgICAgICAgICAgc2FmZS5hZGQoY3ljbGljX25vZGUpCiAgICAgICAgICAgICAgICByZXR1cm4KICAgICAgICAgICAgdmlzaXRlZC5hZGQobm9kZSkKICAgICAgICAgICAgcGF0aC5hcHBlbmQobm9kZSkKICAgICAgICAgICAgZm9yIG5laWdoYm9yIGluIGdyYXBoW25vZGVdOgogICAgICAgICAgICAgICAgZGZzKG5laWdoYm9yLCBwYXRoKQogICAgICAgICAgICBwYXRoLnBvcCgpCgogICAgICAgIGZvciBpIGluIHJhbmdlKG4pOgogICAgICAgICAgICBmb3IgaiBpbiByYW5nZShtKToKICAgICAgICAgICAgICAgIGlmIChpLCBqKSBub3QgaW4gdmlzaXRlZDoKICAgICAgICAgICAgICAgICAgICBkZnMoKGksIGopLCBbXSkKICAgICAgICAKICAgICAgICByZXR1cm4gbGVuKHNhZmUpCiAgICAKICAgICMg5om+5Yiw5omA5pyJIGA/YCDnmoTkvY3nva4KICAgIHF1ZXN0aW9uX3Bvc2l0aW9ucyA9IFsoaSwgaikgZm9yIGkgaW4gcmFuZ2UobikgZm9yIGogaW4gcmFuZ2UobSkgaWYgbWF0cml4W2ldW2pdID09ICc/J10KICAgIG1heF9zYWZlX2NlbGxzID0gMAoKICAgICMg5p6a6IiJ5omA5pyJ5Y+v6IO955qE5pa55ZCR5YiG6YWNCiAgICBmb3IgcmVwbGFjZW1lbnRzIGluIHByb2R1Y3QoIlVETFIiLCByZXBlYXQ9bGVuKHF1ZXN0aW9uX3Bvc2l0aW9ucykpOgogICAgICAgICMg5pu/5o+bIGA/YCDngrrnibnlrprmlrnlkJEKICAgICAgICBuZXdfbWF0cml4ID0gW2xpc3Qocm93KSBmb3Igcm93IGluIG1hdHJpeF0KICAgICAgICBmb3IgKGksIGopLCBkaXJlY3Rpb24gaW4gemlwKHF1ZXN0aW9uX3Bvc2l0aW9ucywgcmVwbGFjZW1lbnRzKToKICAgICAgICAgICAgbmV3X21hdHJpeFtpXVtqXSA9IGRpcmVjdGlvbgogICAgICAgIG1heF9zYWZlX2NlbGxzID0gbWF4KG1heF9zYWZlX2NlbGxzLCBjYWxjdWxhdGVfc2FmZV9jZWxscyhuZXdfbWF0cml4KSkKICAgIAogICAgcmV0dXJuIG1heF9zYWZlX2NlbGxzCgojIOWkmuethua4rOippuizh+aWmei8uOWFpeiZleeQhgpkZWYgcHJvY2Vzc190ZXN0X2Nhc2VzKHRlc3RfY2FzZXMpOgogICAgcmVzdWx0cyA9IFtdCiAgICBmb3IgY2FzZSBpbiB0ZXN0X2Nhc2VzOgogICAgICAgIHJlc3VsdHMuYXBwZW5kKGNvdW50X3NhZmVfY2VsbHMoY2FzZSkpCiAgICByZXR1cm4gcmVzdWx0cwoKIyDmuKzoqabmoYjkvosKdCA9IGludChpbnB1dCgi6KuL6Ly45YWl5ris6Kmm6LOH5paZ5pW46YePOiAiKSkKdGVzdF9jYXNlcyA9IFtdCmZvciBfIGluIHJhbmdlKHQpOgogICAgbiwgbSA9IG1hcChpbnQsIGlucHV0KCLoq4vovLjlhaXnn6npmaPlpKflsI8gbiBtOiAiKS5zcGxpdCgpKQogICAgbWF0cml4ID0gW2lucHV0KCLoq4vovLjlhaXnn6npmaPnrKwge30g6KGMOiAiLmZvcm1hdChpICsgMSkpIGZvciBpIGluIHJhbmdlKG4pXQogICAgdGVzdF9jYXNlcy5hcHBlbmQobWF0cml4KQoKIyDomZXnkIbkuKbovLjlh7rntZDmnpwKcmVzdWx0cyA9IHByb2Nlc3NfdGVzdF9jYXNlcyh0ZXN0X2Nhc2VzKQpmb3IgaWR4LCByZXN1bHQgaW4gZW51bWVyYXRlKHJlc3VsdHMpOgogICAgcHJpbnQoZiLmuKzos4cge2lkeCArIDF9IOeahOWuieWFqOagvOWtkOaVuOmHj+eCujoge3Jlc3VsdH0iKQo=