October 28Medium

Minimum xor path in a grid

DP
Bit Manipulation
Matrix

Problem

You are given a 2D integer array grid of size m * n.

You start at the top-left cell (0, 0) and want to reach the bottom-right cell (m - 1, n - 1).

At each step, you may move either right or down.

The cost of a path is defined as the bitwise XOR of all the values in the cells along that path, including the start and end cells.

Return the minimum possible XOR value among all valid paths from (0, 0) to (m - 1, n - 1).

Solution

class Solution:
    def minCost(self, grid: list[list[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = [[set() for _ in range(n)] for _ in range(m)] 
        dp[0][0].add(grid[0][0])

        for i in range(0, m):
            for j in range(0, n):
                if j:
                    for value in dp[i][j-1]:
                        dp[i][j].add(value ^ grid[i][j])
                if i:
                    for value in dp[i-1][j]:
                        dp[i][j].add(value ^ grid[i][j])

        return min(dp[-1][-1])