โปรแกรมหาตำแหน่งที่ลูกบอลตกในกล่องกริดใน Python

ปัญหา

กริด m x n แต่ละเซลล์มีแผ่นแท้งมุม: 1 = มุมซ้ายบน-ขวาล่าง, -1 = มุมขวาบน-ซ้ายล่าง วางลูกบอลที่เซลล์บนสุดแต่ละคอลัมน์ หาว่าลูกบอลตกออกด้านล่างได้หรือไม่ (คืนคอลัมน์ปลายทาง) หรือติด (-1)

ตัวอย่าง

mat = [[1,1,1,-1],[-1,1,1,-1],[1,-1,-1,1],[1,-1,1,-1]] → ผลลัพธ์ [-1,-1,-1,-1] (ลูกบอลทุกลูกติด)

ขั้นตอนการแก้ปัญหา

1. i, j := rows, cols
2. res := []
3. สำหรับ val 0 ถึง j-1:
   • x := val
   • วน r 0 ถึง i-1:
     • s := mat[r][x]
     • x += mat[r][x]
     • ถ้า x < 0 or x >= j or mat[r][x] != s: res.append(-1); break
   • ถ้าไม่ break: res.append(x)
4. คืน res

การนำไปใช้งาน (Python)

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]]))

อินพุต

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

เอาต์พุต

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