<p>You are given a 2D matrix <code>grid</code> of size <code>n x n</code>. Initially, all cells of the grid are colored white. In one operation, you can select any cell of indices <code>(i, j)</code>, and color black all the cells of the <code>j<sup>th</sup></code> column starting from the top row down to the <code>i<sup>th</sup></code> row.</p>

<p>The grid score is the sum of all <code>grid[i][j]</code> such that cell <code>(i, j)</code> is white and it has a horizontally adjacent black cell.</p>

<p>Return the <strong>maximum</strong> score that can be achieved after some number of operations.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">grid = [[0,0,0,0,0],[0,0,3,0,0],[0,1,0,0,0],[5,0,0,3,0],[0,0,0,0,2]]</span></p>

<p><strong>Output:</strong> <span class="example-io">11</span></p>

<p><strong>Explanation:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2024/05/11/one.png" style="width: 300px; height: 200px;" />
<p>In the first operation, we color all cells in column 1 down to row 3, and in the second operation, we color all cells in column 4 down to the last row. The score of the resulting grid is <code>grid[3][0] + grid[1][2] + grid[3][3]</code> which is equal to 11.</p>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">grid = [[10,9,0,0,15],[7,1,0,8,0],[5,20,0,11,0],[0,0,0,1,2],[8,12,1,10,3]]</span></p>

<p><strong>Output:</strong> <span class="example-io">94</span></p>

<p><strong>Explanation:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2024/05/11/two-1.png" style="width: 300px; height: 200px;" />
<p>We perform operations on 1, 2, and 3 down to rows 1, 4, and 0, respectively. The score of the resulting grid is <code>grid[0][0] + grid[1][0] + grid[2][1] + grid[4][1] + grid[1][3] + grid[2][3] + grid[3][3] + grid[4][3] + grid[0][4]</code> which is equal to 94.</p>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;=&nbsp;n == grid.length &lt;= 100</code></li>
	<li><code>n == grid[i].length</code></li>
	<li><code>0 &lt;= grid[i][j] &lt;= 10<sup>9</sup></code></li>
</ul>

import numpy as np

class Solution:
    # zigzag max weight path 
    def maximumScore(self, grid: List[List[int]]) -> int:
        n = len(grid)
        if n==1: return 0
        grid = np.transpose(grid) # transpose
        ri = [[-1]*n for i in range(n)] # go right
        le = [[-1]*n for i in range(n)] # go left
        for i in range(n):
            ri[i][0] = grid[i][0] # start at each row
        le[1][n-1] = grid[1][n-1] # first row black, start at (1,n-1)
        for i in range(n-1):
            # go right
            for j in range(n-1):
                if ri[i][j]==-1: continue
                ri[i][j+1] = max(ri[i][j+1],ri[i][j]+grid[i][j+1])
                if i+1<n-1:
                    ri[i+1][j+1] = max(ri[i+1][j+1],ri[i][j]+grid[i+1][j+1])
            if i+2<n:
                le[i+2][-1] = max(le[i+2][-1],ri[i][-1]+grid[i+2][-1])
            if i+3<n:
                le[i+3][-1] = max(le[i+3][-1],ri[i][-1]+grid[i+3][-1])
            if i+4<n: # i+1 and i+3 are black
                le[i+4][n-1]=max(le[i+4][-1],ri[i][-1]+grid[i+4][-1]+sum(grid[i+2]))
            # go left
            for j in range(n-1,0,-1):
                if le[i][j]==-1: continue
                le[i][j-1] = max(le[i][j-1],le[i][j]+grid[i][j-1])
                le[i+1][j-1] = max(le[i+1][j-1],le[i][j]+grid[i+1][j-1])
            if i+1<n: # must go right at next row, no 3 white row
                ri[i+1][0] = max(ri[i+1][0],le[i][0]+grid[i+1][0])
        #
        for j in range(n-1,0,-1): # last row, only go left
            if le[-1][j]==-1: continue
            le[-1][j-1] = max(le[-1][j-1],le[-1][j]+grid[-1][j-1])
        imax1 = max(ri[i][-1] for i in range(n))
        imax2 = max(le[i][0] for i in range(n))
        return max(imax1,imax2)

29900