uber oa - even sum paths

'''
A20251204_uberOA


given you a matrix of  m*n rows all positive integers
task is to find the number of even sum paths from 0,0 to m-1,n-1
you can only move down or right at any point in time

------------------------------------------------------------------------------------------------------
important thing to be noted here is -

you know

e+e = e
o+o = e
e+o = o

cool
using this
you can simply solve this with dp
say
if curr is odd
dp[i][j][o] = dp[i-1][j][e] + dp[i][j-1][e]
dp[i][j][e] = dp[i-1][j][o] + dp[i][j-1][o]

if curr is even
dp[i][j][o] = dp[i-1][j][o] + dp[i][j-1][o]
dp[i][j][e] = dp[i-1][j][e] + dp[i][j-1][e]

that's it problem solved
return the final ans at m-1 and n-1


'''

class Solution:
    def withinLimits(self,i,j,m,n):
        return 0<=i<m and 0<=j<n

    def maxEvenSumPaths(self,mat):
        m = len(mat)
        n = len(mat[0])
        dp = [[[0,0] for j in range(n)] for i in range(m)]
        o = 0
        e = 1
        if mat[0][0]%2 == 0:
            dp[0][0][e] = 1
        else:
            dp[0][0][o] = 1


        for i in range(m):
            for j in range(n):
                curr = mat[i][j]
                leftyOdd = 0
                leftyEven = 0
                topyOdd = 0
                topyEven = 0

                if self.withinLimits(i-1,j,m,n):
                    leftyEven = dp[i-1][j][e]
                    leftyOdd = dp[i-1][j][o]
                if self.withinLimits(i,j-1,m,n):
                    topyOdd = dp[i][j-1][o]
                    topyEven = dp[i][j-1][e]

                if curr%2 != 0:
                    dp[i][j][o] += leftyEven + topyEven
                    dp[i][j][e] += leftyOdd + topyOdd
                else:
                    dp[i][j][o] += leftyOdd + topyOdd
                    dp[i][j][e] += leftyEven + topyEven

        return dp[m-1][n-1][e]

if __name__ == "__main__":
    sol = Solution()
    test_cases = [
        # (mat, description)
        # Happy: 2x2, all even, all paths have even sum
        ([[2, 4], [6, 8]], "2x2 all even, all paths even sum"),
        # Happy: 2x2, all odd, only diagonal paths have even sum
        ([[1, 3], [5, 7]], "2x2 all odd, diagonal paths have even sum"),
        # Hard: 3x3, mixed even and odd
        ([[1, 2, 3], [4, 5, 6], [7, 8, 9]], "3x3 mixed even and odd"),
        # Happy: 1x4, horizontal path only
        ([[1, 2, 3, 4]], "1x4 horizontal path only"),
        # Happy: 4x1, vertical path only
        ([[1], [2], [3], [4]], "4x1 vertical path only"),
        # Hard: 3x3, all even
        ([[2, 4, 6], [8, 10, 12], [14, 16, 18]], "3x3 all even"),
        # Hard: 3x3, all odd
        ([[1, 3, 5], [7, 9, 11], [13, 15, 17]], "3x3 all odd"),
        # Edge: 1x1, single cell even
        ([[2]], "1x1 single cell even"),
        # Edge: 1x1, single cell odd
        ([[1]], "1x1 single cell odd"),
        # Hard: 4x4, strategic placement
        ([[1, 2, 1, 2], [2, 1, 2, 1], [1, 2, 1, 2], [2, 1, 2, 1]], "4x4 checkerboard pattern"),
    ]

    for idx, (mat, desc) in enumerate(test_cases, start=1):
        try:
            result = sol.maxEvenSumPaths(mat)
        except Exception as e:
            result = f"Error: {e}"
        print(f"Test case {idx}: {desc}")
        for row in mat:
            print(row)
        print(f"-> Even sum paths: {result}\n")