B2: 土星環模擬：二維陣列與矩陣操作

你的探險隊正在接近土星！為了安全穿越土星環，需要建立一個三維空間模擬系統。土星環可以用二維網格表示，每個格子記錄該區域的冰晶密度。你需要學會處理這種「表格式」的數據結構。

• 二維陣列（矩陣）的創建與操作
• 前綴和技巧：快速計算區域總和
• 差分陣列：高效處理區間更新
• 矩陣遍歷的各種模式

什麼是二維陣列？

二維陣列就像一個表格或棋盤，有行（row）和列（column）：

    列0  列1  列2  列3
行0  5    8    2    9
行1  3    7    1    4
行2  6    2    8    5

創建二維陣列

# ✅ 正確方法：每行都是獨立的列表
matrix = [[0 for _ in range(cols)] for _ in range(rows)]
# ❌ 錯誤方法：所有行都指向同一個列表！
matrix_wrong = [[0]  cols]  rows  # 危險！

matrix = [[0]  3]  2
matrix[0][0] = 5
print(matrix)  # [[5, 0, 0], [5, 0, 0]] - 兩行都被修改了！

前綴和（Prefix Sum）

前綴和是一種「空間換時間」的技巧，可以在 O(1) 時間內計算任意區間的總和。

arr = [1, 2, 3, 4, 5]
# 前綴和：[0, 1, 3, 6, 10, 15]
# prefix[i] = arr[0] + arr[1] + ... + arr[i-1]
# 計算 arr[1:4] 的總和
sum_1_to_3 = prefix[4] - prefix[1]  # 9

差分陣列（Difference Array）

差分陣列用於高效處理「區間增減」操作：

# 對區間 [L, R] 的所有元素 +x
diff[L] += x
diff[R+1] -= x
# 最後還原陣列
for i in range(1, n):
    arr[i] = arr[i-1] + diff[i]

範例 1：土星環密度地圖

import sys
# 任務：創建並顯示土星環密度地圖
rows = int(sys.stdin.readline())
cols = int(sys.stdin.readline())
# 創建二維陣列
density_map = []
for i in range(rows):
    row = list(map(int, sys.stdin.readline().strip().split()))
    density_map.append(row)
# 顯示地圖
print("土星環密度地圖：")
for i in range(rows):
    for j in range(cols):
        print(f"{density_map[i][j]:3}", end=" ")
    print()  # 換行
# 找出最危險區域（密度最高）
max_density = 0
danger_pos = (0, 0)
for i in range(rows):
    for j in range(cols):
        if density_map[i][j] > max_density:
            max_density = density_map[i][j]
            danger_pos = (i, j)
print(f"\n最危險區域：行{danger_pos[0]} 列{danger_pos[1]}")
print(f"密度：{max_density}")

範例 2：矩陣轉置（旋轉視角）

import sys
# 任務：將矩陣轉置（行列互換）
n = int(sys.stdin.readline())
matrix = []
for i in range(n):
    row = list(map(int, sys.stdin.readline().strip().split()))
    matrix.append(row)
# 創建轉置矩陣
transposed = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
    for j in range(n):
        transposed[j][i] = matrix[i][j]
print("原始矩陣：")
for row in matrix:
    print(row)
print("\n轉置後：")
for row in transposed:
    print(row)

範例 3：前綴和 - 快速區域查詢

import sys
# 任務：使用前綴和快速計算子矩陣的總和
n = int(sys.stdin.readline())
matrix = []
for i in range(n):
    row = list(map(int, sys.stdin.readline().strip().split()))
    matrix.append(row)
# 建立二維前綴和
# prefix[i][j] = 從 (0,0) 到 (i-1,j-1) 的矩形區域總和
prefix = [[0 for _ in range(n+1)] for _ in range(n+1)]
for i in range(1, n+1):
    for j in range(1, n+1):
        prefix[i][j] = (matrix[i-1][j-1] + 
                       prefix[i-1][j] + 
                       prefix[i][j-1] - 
                       prefix[i-1][j-1])
# 查詢：計算從 (r1,c1) 到 (r2,c2) 的子矩陣總和
q = int(sys.stdin.readline())  # 查詢次數
for _ in range(q):
    r1, c1, r2, c2 = map(int, sys.stdin.readline().strip().split())
    
    # 轉換為 1-indexed
    r1 += 1
    c1 += 1
    r2 += 1
    c2 += 1
    
    # 使用容斥原理計算
    result = (prefix[r2][c2] - 
             prefix[r1-1][c2] - 
             prefix[r2][c1-1] + 
             prefix[r1-1][c1-1])
    
    print(f"區域 ({r1-1},{c1-1}) 到 ({r2-1},{c2-1}) 總和：{result}")

範例 4：差分陣列 - 隕石雨模擬

import sys
# 任務：模擬多次隕石雨對土星環的影響
n = int(sys.stdin.readline())  # 區域數量
density = [0] * n  # 初始密度都是 0
# 差分陣列
diff = [0] * (n + 1)
# 讀取隕石雨事件
m = int(sys.stdin.readline())  # 事件數量
for _ in range(m):
    L, R, impact = map(int, sys.stdin.readline().strip().split())
    # 對區間 [L, R] 增加 impact
    diff[L] += impact
    diff[R+1] -= impact
# 還原實際密度
for i in range(n):
    if i == 0:
        density[i] = diff[i]
    else:
        density[i] = density[i-1] + diff[i]
print("最終密度分布：")
print(density)
# 找出最危險區域
max_density = max(density)
danger_zones = [i for i, d in enumerate(density) if d == max_density]
print(f"最高密度：{max_density}")
print(f"危險區域：{danger_zones}")

範例 5：螺旋矩陣遍歷

import sys
# 任務：以螺旋方式遍歷矩陣（順時針）
n = int(sys.stdin.readline())
matrix = []
for i in range(n):
    row = list(map(int, sys.stdin.readline().strip().split()))
    matrix.append(row)
result = []
top, bottom = 0, n - 1
left, right = 0, n - 1
while top <= bottom and left <= right:
    # 向右
    for col in range(left, right + 1):
        result.append(matrix[top][col])
    top += 1
    
    # 向下
    for row in range(top, bottom + 1):
        result.append(matrix[row][right])
    right -= 1
    
    # 向左
    if top <= bottom:
        for col in range(right, left - 1, -1):
            result.append(matrix[bottom][col])
        bottom -= 1
    
    # 向上
    if left <= right:
        for row in range(bottom, top - 1, -1):
            result.append(matrix[row][left])
        left += 1
print("螺旋遍歷結果：")
print(result)

關鍵技術點

1. 二維陣列的正確創建

   # 每次迴圈都創建新的列表
   matrix = [[0 for _ in range(cols)] for _ in range(rows)]
   
   # 等價於：
   matrix = []
   for i in range(rows):
       row = []
       for j in range(cols):
           row.append(0)
       matrix.append(row)
   

1. 前綴和的容斥原理

   要計算紅色區域的總和：
   
   +-------+-------+
   |   A   |   B   |
   +-------+-------+
   |   C   | [RED] |
   +-------+-------+
   
   RED = (A+B+C+RED) - (A+B) - (A+C) + A
       = prefix[r2][c2] - prefix[r1-1][c2] 

prefix[r2][c1-1] + prefix[r1-1][c1-1]

   

1. 差分陣列的原理

   # 對區間 [2, 5] 加 3
   diff[2] += 3   # 從位置 2 開始增加
   diff[6] -= 3   # 從位置 6 開始減少
   
   # 還原後：
   # 位置 0,1: 不變
   # 位置 2,3,4,5: +3
   # 位置 6 之後: 不變
   

1. 矩陣遍歷模式
2. 逐行遍歷：for i in range(rows): for j in range(cols)
3. 逐列遍歷：for j in range(cols): for i in range(rows)
4. 對角線遍歷：for i in range(n): matrix[i][i]
5. 螺旋遍歷：使用四個邊界指標