---
# System prepended metadata

title: 4neighbors
tags: [APCS]

---

###### tags: `APCS`
# **4neighbors**
### **題目解析** 
在一個5x5的二維陣列中，搜尋從給定起點出發的連續區域，並計算該區域內的元素個數。這類問題常見於圖形和網格資料結構的遍歷中，例如洪水填充演算法（Flood Fill）或連通分量的計算。這段程式碼將一個 1 視為區域的一部分，並使用深度優先搜索（DFS）來遍歷和標記所有相連的區域。
### **解題方向** 
1. 初始化：
    * 給定一個5x5的二維陣列arr，其中包含0和1。1表示可以通過的區域，而0表示不能通過的區域。
    * 創建一個相同大小的marker陣列來標記已經訪問過的區域。
1. 深度優先搜索（DFS）：
    * 使用遞迴函數search_map從指定的起始位置(2, 2)開始進行DFS遍歷。
    * 在遞迴函數中，首先檢查邊界條件，確保座標(x, y)在陣列範圍內。
    * 如果當前位置是1且未被標記，則標記該位置並向四個方向（上、下、左、右）遞迴搜尋。
1. 計算結果：
    * 搜尋完成後，遍歷marker陣列計算已標記為1的區域數量。
### **完整程式碼**
```python=
# 二維陣列，表示5x5的圖形
arr = [[1, 0, 0, 0, 1],
       [1, 0, 1, 0, 0],
       [0, 1, 1, 1, 0],
       [0, 0, 1, 1, 0],
       [1, 0, 0, 0, 0]]

# 標記陣列，初始為全0，表示未訪問過
marker = [ [0, 0, 0, 0, 0] for x in range(5) ]

# 深度優先搜索函數
def search_map(arr, marker, x, y):
    # 檢查是否在範圍外
    if (x<0 or x>=5) or (y<0 or y>=5):
        return 0
    
    # 如果當前元素是1且未被標記
    elif arr[x][y] == 1 and marker[x][y] == 0:
        # 標記該位置
        marker[x][y] = 1

        # 遞迴搜尋四個方向
        search_map(arr, marker, x-1, y) 
        search_map(arr, marker, x+1, y) 
        search_map(arr, marker, x, y-1) 
        search_map(arr, marker, x, y+1)

# 從(2, 2)開始搜尋
search_map(arr, marker, 2, 2)

# 計算被標記為1的區域數量
c = 0
for i in range(5):
    for j in range(5):
        if marker[i][j] == 1:
            c += 1
            
print(c)  # 輸出區域的大小
```