Giả sử chúng ta có ma trận mat với các giá trị: 0 (ô trống), 1 (bom), 2 (kẻ thù). Bom nổ theo hàng ngang và dọc từ đầu đến cuối. Cần kiểm tra xem tất cả kẻ thù có bị tiêu diệt khi bom nổ hay không.
Ví dụ ma trận 4x4: 0 0 2 0 0 1 0 0 0 2 0 0 0 0 1 0 Đầu ra True vì bom tại [1,1] tiêu diệt kẻ thù tại [2,1], bom tại [3,2] tiêu diệt kẻ thù tại [0,2].
Các bước giải quyết:
- r := số hàng, c := số cột.
- Duyệt mọi ô (i,j):
- Nếu mat[i][j] == 1 (bom):
- Duyệt x từ 0 đến r-1: nếu mat[x][j] != 1, gán mat[x][j] = 0 (tiêu diệt theo cột).
- Duyệt y từ 0 đến c-1: nếu mat[i][y] != 1, gán mat[i][y] = 0 (tiêu diệt theo hàng).
- Nếu mat[i][j] == 1 (bom):
- Duyệt lại ma trận: nếu còn ô nào giá trị 2, trả về False.
- Trả về True.
Xem ví dụ dưới đây để hiểu rõ hơn:
Ví dụ
def solve(mat):
r = len(mat)
c = len(mat[0])
for i in range(r):
for j in range(c):
if mat[i][j] == 1:
for x in range(r):
if mat[x][j] != 1:
mat[x][j] = 0
for y in range(c):
if mat[i][y] != 1:
mat[i][y] = 0
for i in range(r):
for j in range(c):
if mat[i][j] == 2:
return False
return True
matrix = [
[0,0,2,0],
[0,1,0,0],
[0,2,0,0],
[0,0,1,0]
]
print(solve(matrix))
Đầu vào
[ [0,0,2,0], [0,1,0,0], [0,2,0,0], [0,0,1,0] ]
Đầu ra
True