fork download
copy 
  1. from itertools import product
  2.  
  3. def count_safe_cells(matrix):
  4.     n = len(matrix)
  5.     m = len(matrix[0])
  6.  
  7.     # 定義方向映射
  8.     directions = {
  9.         'U': (-1, 0),
  10.         'D': (1, 0),
  11.         'L': (0, -1),
  12.         'R': (0, 1)
  13.     }
  14.  
  15.     def in_bounds(x, y):
  16.         """檢查是否在邊界內"""
  17.         return 0 <= x < n and 0 <= y < m
  18.  
  19.     # 計算給定矩陣的安全格子數量
  20.     def calculate_safe_cells(matrix):
  21.         graph = {}
  22.         for i in range(n):
  23.             for j in range(m):
  24.                 graph[(i, j)] = []
  25.                 if matrix[i][j] in directions:
  26.                     dx, dy = directions[matrix[i][j]]
  27.                     ni, nj = i + dx, j + dy
  28.                     if in_bounds(ni, nj):
  29.                         graph[(i, j)].append((ni, nj))
  30.  
  31.         visited = set()
  32.         safe = set()
  33.  
  34.         def dfs(node, path):
  35.             """深度優先搜索來檢測環並計算安全格子"""
  36.             if node in visited:
  37.                 if node in path:
  38.                     # 發現環，將環內的節點加入安全集合
  39.                     cycle_start = path.index(node)
  40.                     for cyclic_node in path[cycle_start:]:
  41.                         safe.add(cyclic_node)
  42.                 return
  43.             visited.add(node)
  44.             path.append(node)
  45.             for neighbor in graph[node]:
  46.                 dfs(neighbor, path)
  47.             path.pop()
  48.  
  49.         for i in range(n):
  50.             for j in range(m):
  51.                 if (i, j) not in visited:
  52.                     dfs((i, j), [])
  53.  
  54.         return len(safe)
  55.  
  56.     # 找到所有 `?` 的位置
  57.     question_positions = [(i, j) for i in range(n) for j in range(m) if matrix[i][j] == '?']
  58.     max_safe_cells = 0
  59.  
  60.     # 枚舉所有可能的方向分配
  61.     for replacements in product("UDLR", repeat=len(question_positions)):
  62.         # 替換 `?` 為特定方向
  63.         new_matrix = [list(row) for row in matrix]
  64.         for (i, j), direction in zip(question_positions, replacements):
  65.             new_matrix[i][j] = direction
  66.         max_safe_cells = max(max_safe_cells, calculate_safe_cells(new_matrix))
  67.  
  68.     return max_safe_cells
  69.  
  70. # 多筆測試資料輸入處理
  71. def process_test_cases(test_cases):
  72.     results = []
  73.     for case in test_cases:
  74.         results.append(count_safe_cells(case))
  75.     return results
  76.  
  77. # 測試案例
  78. t = int(input("請輸入測試資料數量: "))
  79. test_cases = []
  80. for _ in range(t):
  81.     n, m = map(int, input("請輸入矩陣大小 n m: ").split())
  82.     matrix = [input("請輸入矩陣第 {} 行: ".format(i + 1)) for i in range(n)]
  83.     test_cases.append(matrix)
  84.  
  85. # 處理並輸出結果
  86. results = process_test_cases(test_cases)
  87. for idx, result in enumerate(results):
  88.     print(f"測資 {idx + 1} 的安全格子數量為: {result}")
  89.  
Success #stdin #stdout 0.14s 9868KB
comments (?)
stdin
copy 
3
3 3
UUU
L?R
DDD
2 3
???
???
3 3
?U?
R?L
RDL
stdout
copy 
請輸入測試資料數量: 請輸入矩陣大小 n m: 請輸入矩陣第 1 行: 請輸入矩陣第 2 行: 請輸入矩陣第 3 行: 請輸入矩陣大小 n m: 請輸入矩陣第 1 行: 請輸入矩陣第 2 行: 請輸入矩陣大小 n m: 請輸入矩陣第 1 行: 請輸入矩陣第 2 行: 請輸入矩陣第 3 行: 測資 1 的安全格子數量為: 0
測資 2 的安全格子數量為: 6
測資 3 的安全格子數量為: 2
https://ideone.com/CeSE1U
language:
Python 3 (python  3.9.5)
created:
26 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!