สมมติว่าเรามีเมทริกซ์ไบนารี 2d โดยที่ 1 แทนระเบิดและ 0 แทนเซลล์ว่าง เมื่อระเบิดระเบิด ช่องว่างทั้งหมดในแถวและคอลัมน์เดียวกันจะเสียหาย เราต้องหาจำนวนช่องว่างที่เรายืนได้เพื่อไม่ให้เกิดความเสียหาย
ดังนั้นหากอินพุตเป็นแบบ
| 1 | 1 | 0 |
| 0 | 0 | 0 |
| 0 | 0 | 0 |
จากนั้นผลลัพธ์จะเป็น 2 เนื่องจากเซลล์ด้านขวาล่างและเซลล์ด้านขวาตรงกลางมีช่องว่าง 2 ช่อง
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้:
-
r :=รายการขนาดเท่ากับจำนวนแถวของเมทริกซ์และเติมเท็จ
-
c :=รายการขนาดเท่ากับจำนวนคอลัมน์ของเมทริกซ์และเติมเท็จ
-
สำหรับฉันในช่วง 0 ถึงจำนวนแถวของเมทริกซ์ - 1 ทำ
-
สำหรับ j ในช่วง 0 ถึงจำนวนคอลัมน์ของเมทริกซ์ - 1 ทำ
-
ถ้า matrix[i, j] เท่ากับ 1 แล้ว
-
r[i] :=จริง c[j] :=จริง
-
-
-
-
ct :=0
-
สำหรับฉันในช่วง 0 ถึงจำนวนแถวของเมทริกซ์ - 1 ทำ
-
สำหรับ j ในช่วง 0 ถึงจำนวนคอลัมน์ของเมทริกซ์ - 1 ทำ
-
ถ้า r[i] เป็นเท็จ และ c[j] เป็นเท็จ ดังนั้น
-
ct :=ct + 1
-
-
-
-
ส่งคืน ct
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น:
ตัวอย่าง
class Solution: def solve(self, matrix): r = [False for i in range(len(matrix))] c = [False for i in range(len(matrix[0]))] for i in range(len(matrix)): for j in range(len(matrix[0])): if matrix[i][j] == 1: r[i] = True c[j] = True ct = 0 for i in range(len(matrix)): for j in range(len(matrix[0])): if r[i] == False and c[j] == False: ct += 1 return ct ob = Solution() matrix = [ [1, 1, 0], [0, 0, 0], [0, 0, 0] ] print(ob.solve(matrix))
อินพุต
[ [1, 1, 0], [0, 0, 0], [0, 0, 0] ]
ผลลัพธ์
2
