tags: APCS

e605－Minesweeper

題目連結： e605

題目解析

• 目標：找出每個安全方格（.）周圍的地雷數，並顯示出來。地雷用*表示，安全方格用.表示。
• 輸入：
  • 第一行是兩個整數n和m，代表地圖的行和列。
  • 接下來的n行，每行有m個字符，描述地圖。
  • n = m = 0 表示輸入結束。
• 輸出：
  • 每組測試資料輸出第一行為Field #k:，k是測試資料的編號。
  • 接下來是標記提示的地圖，每筆測資間用空白行分隔。

解題方向

• 輸入資料的處理
  • 讀取多組測試資料：首先，我們需要不斷讀取多組測試資料，直到遇到0 0為止，這表示輸入的結束。
  • 地圖大小：每組測試資料的第一行包含兩個整數n和m，分別代表地圖的行數和列數。
  • 地圖內容：接下來的n行，每行有m個字符，代表地圖的具體內容，其中*表示地雷，.表示安全方格。
• 建立結果矩陣
  • 初始化一個與輸入地圖大小相同的矩陣，用來存放計算後的提示數字。這個矩陣的初始值應設為0。
• 遍歷地圖進行計算
  • 偵測地雷位置：對地圖進行雙重迴圈遍歷，確定每個格子的狀態。
  • 計算提示數字：當找到一個地雷（*）時，對其周圍的八個相鄰方格進行更新。每個相鄰的安全方格的提示數字加1。
  • 邊界檢查：在更新相鄰方格時，需要確保不越過地圖的邊界，這可以通過檢查座標是否在合法範圍內來實現。
• 生成輸出
  • 格式化輸出：為每組測試資料輸出時，首先輸出Field #k:，其中k是當前測試資料的編號。
  • 處理格式差異：確保每組測試資料間用空行分隔，這在格式化輸出中尤為重要。
  • 輸出結果矩陣：遍歷結果矩陣，將地雷位置用*表示，其餘位置輸出計算的提示數字。
• 處理例外和邊界情況
  • 結束條件：當讀入n = m = 0時，應立即停止程式的執行，避免進一步的無效計算。
  • 例外處理：考慮輸入可能出現的錯誤情況，使用例外捕捉來保證程式的穩定性。

程式解析

方向向量：

dx = [1, -1, 0, 0, -1, 1, -1, 1]
dy = [0, 0, 1, -1, 1, 1, -1, -1]

• dx 和 dy 是用來表示相對於當前方格的八個方向（上下左右和四個對角線）的偏移量。

迴圈開始與輸入讀取：

TC = 1  # 測試案例計數器
while True:
    try:
        s = input()
        n, m = map(int, s.split())

        if n == 0 and m == 0:
            break

• TC 用於追踪測試案例的編號。
• 使用無窮迴圈來讀取多組資料，直到輸入0 0時結束。
• 讀取行數n和列數m，如果n和m都是0，則停止輸入。

地圖讀取與初始化：

field = []
for i in range(n):
    s = input()
    field.append(list(s))

result = [[0 for j in range(m)] for i in range(n)]

• field用於存放地圖的每一行。
• result用於存放處理後的結果地圖，初始化為全零的矩陣。

掃描地圖與計算提示數字：

for i in range(n):
    for j in range(m):
        if field[i][j] == '*':
            result[i][j] = -1
        else:
            for k in range(8):
                x = i + dx[k]
                y = j + dy[k]
                if x >= 0 and x < n and y >= 0 and y < m and field[x][y] == "*":
                    result[i][j] += 1

• 雙重迴圈遍歷地圖的每一個格子。
• 如果格子是地雷（*），將結果對應位置標記為-1。
• 否則，檢查該格子周圍八個相鄰的格子。
• x和y是計算後的相鄰格子座標，確認不超出邊界並且是地雷時，對結果計數加1。

格式化輸出：

if TC > 1:
    print()
print("Field #"+str(TC)+":")

TC += 1
for i in range(n):
    for j in range(m):
        if result[i][j] == -1:
            print("*", end='')
        else:
            print(result[i][j], end='')
    print()

• 如果TC大於1，則打印空行作為測試案例的分隔符。
• 打印Field #k:來標示測試案例。
• TC增量1，用於下次測試案例的編號。
• 再次遍歷result矩陣，輸出每個方格的值。-1的方格輸出*，其他方格輸出其數字。

完整程式碼

# 定義方向向量，用於檢查周圍八個方格
dx = [1, -1, 0, 0, -1, 1, -1, 1]
dy = [0, 0, 1, -1, 1, 1, -1, -1]

TC = 1  # 測試案例計數器
while True:
    try:
        # 讀取地圖尺寸
        s = input()
        n, m = map(int, s.split())

        # 如果 n = m = 0, 結束輸入
        if n == 0 and m == 0:
            break

        field = []  # 用來存放地圖
        for i in range(n):
            s = input()
            field.append(list(s))

        # 初始化結果地圖，以 0 表示
        result = [[0 for j in range(m)] for i in range(n)]

        # 掃描整個地圖
        for i in range(n):
            for j in range(m):
                # 如果是地雷，標記為 -1
                if field[i][j] == '*':
                    result[i][j] = -1
                else:
                    # 檢查周圍八個方格
                    for k in range(8):
                        x = i + dx[k]
                        y = j + dy[k]
                        # 檢查邊界並確認是否有地雷
                        if x >= 0 and x < n and y >= 0 and y < m and field[x][y] == "*":
                            result[i][j] += 1

        # 格式化輸出
        if TC > 1:
            print()  # 輸出測試案例間的空行
        print("Field #"+str(TC)+":")

        TC += 1  # 測試案例編號遞增
        for i in range(n):
            for j in range(m):
                # 如果是地雷，顯示 *
                if result[i][j] == -1:
                    print("*", end='')
                else:
                    # 否則顯示周圍地雷數
                    print(result[i][j], end='')
            print()  # 每行結束後換行

    except:
        break