สมมติว่าเรามีเมทริกซ์ไบนารี โดยที่ 1 หมายถึงดิน และ 0 หมายถึงน้ำ จากดินแดนใด ๆ เราสามารถเลื่อนขึ้น ลง ซ้ายหรือขวา แต่ไม่เป็นแนวทแยงไปยังเซลล์พื้นดินอื่นหรือออกจากเมทริกซ์ เราต้องหาจำนวนเซลล์ภาคพื้นดินที่เราไม่สามารถออกจากเมทริกซ์ได้
ดังนั้นหากอินพุตเป็นแบบ
| 0 | 0 | 0 | 1 |
| 0 | 1 | 1 | 0 |
| 0 | 1 | 1 | 0 |
| 0 | 0 | 0 | 1 |
จากนั้นผลลัพธ์จะเป็น 4 เนื่องจากมีสี่เหลี่ยมดิน 4 ช่องอยู่ตรงกลางซึ่งเราไม่สามารถเดินออกจากเมทริกซ์ได้
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- q :=รายการคู่ (i, j) สำหรับแต่ละแถว i และคอลัมน์เมื่อ matrix[i, j] คือ land i และ j เป็นดัชนีเส้นขอบ
- idx :=0
- สำหรับแต่ละคู่ (x, y) ใน q ทำ
- เมทริกซ์[x, y] :=0
- ในขณะที่ idx <ขนาดของ q ทำ
- x, y :=q[idx]
- สำหรับแต่ละ (dx, dy) ใน [(-1, 0) ,(0, -1) ,(0, 1) ,(1, 0) ] ทำ
- nx :=x + dx
- ny :=y + dy
- ถ้า 0 <=nx <จำนวนแถวของเมทริกซ์และ 0 <=ny <จำนวนคอลัมน์ของเมทริกซ์[nx] และเมทริกซ์[nx, ny] คือ 1 ดังนั้น
- เมทริกซ์[nx, ny] :=0
- แทรก (nx, ny) ที่ส่วนท้ายของ q
- idx :=idx + 1
- ส่งคืนผลรวมขององค์ประกอบทั้งหมดของเมทริกซ์
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
def solve(matrix): q = [(i, j) for i in range(len(matrix)) for j in range(len(matrix[i])) if matrix[i][j] and (i == 0 or i == len(matrix) - 1 or j == 0 or j == len(matrix[i]) - 1)] idx = 0 for x, y in q: matrix[x][y] = 0 while idx < len(q): x, y = q[idx] for dx, dy in [(-1, 0), (0, -1), (0, 1), (1, 0)]: nx, ny = x + dx, y + dy if 0 <= nx < len(matrix) and 0 <= ny < len(matrix[nx]) and matrix[nx][ny]: matrix[nx][ny] = 0 q.append((nx, ny)) idx += 1 return sum(sum(row) for row in matrix) matrix = [ [0, 0, 0, 1], [0, 1, 1, 0], [0, 1, 1, 0], [0, 0, 0, 1] ] print(solve(matrix))
อินพุต
[ [0, 0, 0, 1], [0, 1, 1, 0], [0, 1, 1, 0], [0, 0, 0, 1] ]
ผลลัพธ์
4
