Chương trình tìm vị trí quả bóng rơi trong hộp lưới trong Python

Cho lưới m x n, mỗi ô có vách chéo: 1 = từ trên-trái đến dưới-phải, -1 = từ trên-phải đến dưới-trái. Thả bóng từ mỗi ô hàng đầu, mô phỏng chuyển động. Trả về mảng cột cuối cùng (hoặc -1 nếu kẹt).

Ví dụ: ma trận 4x4 cho trước → tất cả bóng kẹt → [-1, -1, -1, -1].

Giải thuật (Mô phỏng)

1. Với mỗi cột bắt đầu val (0..n-1):
   • x = val.
   • Duyệt hàng r từ 0 đến m-1:
     • s = mat[r][x] (hướng vách).
     • x += s (di chuyển sang trái/phải).
     • Nếu x ra ngoài hoặc mat[r][x] != s (vách đối diện chặn) → kẹt, ghi -1, break.
   • Nếu không kẹt: ghi x.

Ví dụ minh họa

def solve(mat):
    i, j = len(mat), len(mat[0])
    res = []
    for val in range(j):
        x = val
        for r in range(i):
            s = mat[r][x]
            x += mat[r][x]
            if x < 0 or x >= j or mat[r][x] != s:
                res.append(-1)
                break
        else:
            res.append(x)
    return res

print(solve([[1, 1, 1, -1], [-1, 1, 1, -1], [1, -1, -1, 1], [1, -1, 1, -1]]))

Đầu vào

[[1, 1, 1, -1], [-1, 1, 1, -1], [1, -1, -1, 1], [1, -1, 1, -1]]

Đầu ra

[-1, -1, -1, -1]