Chương trình tìm số vị trí đặc biệt trong ma trận nhị phân bằng Python

Giả sử ta có ma trận nhị phân m x n, tìm số vị trí đặc biệt (special positions). Vị trí (i,j) đặc biệt khi mat[i][j] = 1 và tất cả phần tử khác trong hàng i và cột j đều là 0.

Ví dụ ma trận 4x5:

Giải thuật

1. special := 0
2. For i từ 0 đến row count - 1:
   • Nếu matrix[i].count(1) == 1:
     • numOfOne := 0
     • indexOfOne := matrix[i].index(1)
     • For j từ 0 đến col size - 1:
       • Nếu matrix[j][indexOfOne] == 1: numOfOne++
       • Nếu numOfOne > 1: break
     • Nếu numOfOne == 1: special++
3. Trả về special

Ví dụ (Python)

def solve(matrix):
    special = 0
    for i in range(len(matrix)):
        if matrix[i].count(1) == 1:
            numOfOne = 0
            indexOfOne = matrix[i].index(1)
            for j in range(len(matrix)):
                if matrix[j][indexOfOne] == 1:
                    numOfOne += 1
                if numOfOne > 1:
                    break
            if numOfOne == 1:
                special += 1
    return special

matrix = [
    [1,0,0,0,0],
    [0,0,1,0,0],
    [0,0,0,1,1],
    [0,1,0,0,0]
]
print(solve(matrix))

Input

[[1,0,0,0,0], [0,0,1,0,0], [0,0,0,1,1], [0,1,0,0,0]]

Output

3