2019/09/24（二）【ITSA】[C_AR04-易] 邊緣偵測

    近期因為教學工作有接觸到解題相關的部分，不過我對解題的歷程是這樣的，我本身不是由這條路（解題）培養起來程式能力的，而是走算很 Hardcore 的路線讀學術書，哪科沒修過就修，所以解題需要的技巧，還要時間來培養培養，那就回到幾個解題網站練個手。

題目

問題描述 ：

      一個二元圖形通常用一個二維陣列表示，其中的值為0或1，即為淺色（以1表）圖形在深色（以0表）的背景中。在分析圖形時往往需要找出其邊緣，稱之為邊緣偵測。所謂”邊緣”即為一個1的pixel其上下左右至少有一個為0。寫一個程式讀入二元圖形，輸出該圖之邊緣。

輸入說明 ：

      第一行為一個正整數N，代表共有幾組測試資料。之後接下來有N組數據，每組第一行為兩個正整數n及m，表示二元圖形的大小為n×m的矩陣，之後n行每行有m個數字（1 ≤ n,m ≤ 100 ，每個數字後面都有一個空格字元），分別是0或1，即為該組測試資料之二元圖形。

輸出說明 ：

      將不是邊緣的點以底線‘_’表示，邊緣的點則以0表示，每組測資答案按照該組測資給予的 矩陣大小輸出於n行，每輸出一個點，後面即輸出空格。每組測試資料結果與前一組之間空一行。

範例 ：

Sample Input:	Sample Output:
2 5 7 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 1 1 1 1 1 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 8 11 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 1 1 0 1 1 1 1 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0	_ _ _ _ _ _ _ _ _ 0 0 0 _ _ _ 0 _ _ _ 0 _ _ _ 0 0 0 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 0 0 _ _ _ 0 0 _ _ _ 0 _ _ 0 _ 0 _ _ 0 _ _ _ 0 _ _ 0 _ _ 0 _ _ _ _ _ 0 _ _ _ 0 _ _ _ _ _ _ _ 0 _ 0 _ _ _ _ _ _ _ _ _ 0 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _

解題

這題主要有幾個重點：

1. 輸入格式：在題目中的輸入說明有提到「每個數字後面都有一個空格字元」，這點一定要好好注意，因為一開始沒注意到，加上我的輸入習慣是在最後一個字元通常不會加上空格，因此在此處吃了不少苦頭。
2. 輸出格式：這部分在題目中也有提及，「每組測試資料結果與前一組之間空一行」，調整空行不是難事，但仍需多加注意。
3. 解題策略：這題的想法乍看之下有些難，但其實很容易，我們既然要的是處於邊緣的 1 被留下來，那就是去觀察在邊緣的 1 與不在邊緣的 1 差別在哪，那相當明顯的，若是在邊緣的 1，在上下左右任意位置，一定至少有一個 0；反之填滿於圖形中的 1 則不會有上述狀況，因此我們可以利用此點作為設計本題演算法的基礎。

程式碼

實作環境：Windows 10, Python 3.6.7

    下方為程式碼，但其實發展順序是倒過來的，最後一段程式碼是我一開始看到題目後，簡單寫下處理步驟，以及將可以抽離成函式的功能獨立出來設計，算是沒有經過整理、最初段的程式碼；後來依序往上（第一、二段）的程式碼就是依照題目要求簡化的。
    由於這種解題的內容重點是著重在演算法、資料結構以及對於所使用的語言本身的熟悉程度，寫作風格以及維護性就不是重點，所以第一段的程式碼雖然是我最不喜歡，即沒有對可用功能進行封裝或是隔離的處理，但是卻不失為解題當下的好解答之一。

# code phase 1
while True:
    try:
        num = int(input())
        for step in range(num):
            row, col = (int(n) for n in input().split())

            graph = []
            for i in range(row):
                lt = [int(n) for n in input().split()]
                graph.append(lt)
            
            for i in range(row):
                for j in range(col):
                    if graph[i][j] == 0:
                        print("_ ", end='')
                    else:
                        if i>0 and graph[i-1][j]==0:
                            print("0 ", end='')
                        elif i<row-1 and graph[i+1][j]==0:
                            print("0 ", end='')
                        elif j>0 and graph[i][j-1]==0:
                            print("0 ", end='')
                        elif j<col-1 and graph[i][j+1]==0:
                            print("0 ", end='')
                        else:
                            print("_ ", end='')
                print()
            if step != num-1: 
                print()
    except:
        break

# code phase 2
def edge_detect(arrs, row, col):
    for i in range(row):
        for j in range(col):
            if arrs[i][j]:
                if i>0 and not(arrs[i-1][j]):
                    print("0 ", end='')
                elif i<row-1 and not(arrs[i+1][j]):
                    print("0 ", end='')
                elif j>0 and not(arrs[i][j-1]):
                    print("0 ", end='')
                elif j<col-1 and not(arrs[i][j+1]):
                    print("0 ", end='')
                else:
                    print("_ ", end='')
            else:
                print("_ ", end='')
        print()

while True:
    try:
        n = int(input())
        for step in range(n):
            scale = [int(num) for num in input().split()]
            graph = list()
            for row in range(scale[0]):
                col = [int(num) for num in input().split()]
                graph.append(col)
            edge_detect(graph, scale[0], scale[1])
            if step != n-1:
                print()

    except EOFError as e:
        break

# code phase 3
def print_arr(arrs):
    for inner in arrs:
        for ch in inner:
            print(f"{ch}", end='')
        print()

def check(i: int, j: int, n: int, m: int):
    if i<0 or i>n-1 or j<0 or j>m-1:
        return False
    return True

def edge_detect(arrs, row, col):
    for i in range(row):
        for j in range(col):
            if arrs[i][j]:
                if check(i-1, j, row, col):
                    if not(arrs[i-1][j]):
                        arrs[i][j] = 1
                        continue
                if check(i+1, j, row, col):
                    if not(arrs[i+1][j]):
                        arrs[i][j] = 1
                        continue
                if check(i, j-1, row, col):
                    if not(arrs[i][j-1]):
                        arrs[i][j] = 1
                        continue
                if check(i, j+1, row, col):
                    if not(arrs[i][j+1]):
                        arrs[i][j] = 1
                        continue
                arrs[i][j] = 2
    return arrs


def transfer(arrs, row, col):
    for i in range(row):
        for j in range(col):
            if arrs[i][j] == 2 or arrs[i][j] == 0:
                arrs[i][j] = "_ "
            else:
                arrs[i][j] = "0 "
    return arrs


if __name__ == "__main__":
    while True:
        try:
            n = int(input())
            for step in range(n):
                scale = [int(num) for num in input().split()]
                graph = list()
                for row in range(scale[0]):
                    lt = [int(num) for num in input().split()]
                    graph.append(lt)
                graph = edge_detect(graph, scale[0], scale[1])
                graph = transfer(graph, scale[0], scale[1])
                print_arr(graph)
                if step != n-1:
                    print()
        except EOFError as e:
            break