LC 1102 [M] Path With Maximum Minimum Value - ALawliet/algorithms GitHub Wiki

it is greedy and uses weight like Dijkstra

using the priority and visited, we can store the min and choose the max at the same time

5 (-5, (0, 0)) [1, 0, 0], [0, 0, 0], [0, 0, 0](/ALawliet/algorithms/wiki/1,-0,-0],-[0,-0,-0],-[0,-0,-0)
	 -1 (1, 0)
	 -4 (0, 1)
4 (-4, (0, 1)) [1, 1, 0], [1, 0, 0], [0, 0, 0](/ALawliet/algorithms/wiki/1,-1,-0],-[1,-0,-0],-[0,-0,-0)
	 -2 (1, 1)
	 -5 (0, 2)
5 (-4, (0, 2)) [1, 1, 1], [1, 1, 0], [0, 0, 0](/ALawliet/algorithms/wiki/1,-1,-1],-[1,-1,-0],-[0,-0,-0)
	 -6 (1, 2)
6 (-4, (1, 2)) [1, 1, 1], [1, 1, 1], [0, 0, 0](/ALawliet/algorithms/wiki/1,-1,-1],-[1,-1,-1],-[0,-0,-0)
	 -6 (2, 2)
6 (-4, (2, 2)) [1, 1, 1], [1, 1, 1], [0, 0, 1](/ALawliet/algorithms/wiki/1,-1,-1],-[1,-1,-1],-[0,-0,-1)

from queue import PriorityQueue

DIRS = ((1,0),(0,1),(-1,0),(0,-1))

class Solution:
    def maximumMinimumPath(self, grid: List[List[int]]) -> int:
        n_rows = len(grid)
        n_cols = len(grid[0])
        
        Q = PriorityQueue()
        Q.put( (-grid[0][0], 0, 0) ) # score, r, c
        visited = [ [0 for _ in range(n_cols)] for _ in range(n_rows)]
        visited[0][0] = 1
        
        while Q:
            score, r, c = Q.get()
            # print(grid[r][c], (score, (r, c)), visited)
            
            if r == n_rows - 1 and c == n_cols - 1:
                return -score
            
            for dr, dc in DIRS:
                nr, nc = r + dr, c + dc
                if 0 <= nr < n_rows and 0 <= nc < n_cols and not visited[nr][nc]:
                    min_score = max(score, -grid[nr][nc])
                    # print('\t', -grid[nr][nc], (nr, nc))
                    Q.put( (min_score, nr, nc) )
                    visited[nr][nc] = 1