LeetCode/cs/maximum-number-of-points-from-grid-queries.cs

public class Solution {
    private static readonly List<(int dy, int dx)> DIRECTIONS = [
        (0, 1),
        (0, -1),
        (1, 0),
        (-1, 0)
    ];

    private int[] Dijkstra(int[][] grid) {
        var thresholds = new int[grid.Length * grid[0].Length + 1];

        var minToReach = new int[grid.Length * grid[0].Length];
        Array.Fill(minToReach, int.MaxValue);
        minToReach[Index(0, 0)] = grid[0][0];

        var q = new PriorityQueue<(int y, int x), int>();
        q.Enqueue((0, 0), grid[0][0]);

        var visited = 0;
        while (q.TryDequeue(out var pos, out var threshold)) {
            thresholds[++visited] = threshold;

            foreach (var direction in DIRECTIONS) {
                var y = pos.y + direction.dy;
                var x = pos.x + direction.dx;

                if (y < 0 || y >= grid.Length || x < 0 || x >= grid[y].Length || minToReach[Index(y, x)] != int.MaxValue) {
                    continue;
                }

                minToReach[Index(y, x)] = Math.Max(threshold, grid[y][x]);
                q.Enqueue((y, x), minToReach[Index(y, x)]);
            }
        }

        return thresholds;

        int Index(int y, int x) => y * grid[0].Length + x;
    }

    private int[] ProcessQueries(int[] queries, int upperBound, int[] thresholdForMax) {
        return queries.Select(q => Find(q)).ToArray();

        int Find(int threshold) {
            var (left, right) = (0, upperBound);
            while (left < right) {
                var mid = left + (right - left + 1) / 2;
                if (thresholdForMax[mid] < threshold) {
                    left = mid;
                } else {
                    right = mid - 1;
                }
            }

            return left;
        }
    }

    public int[] MaxPoints(int[][] grid, int[] queries) {
        var thresholdForMax = Dijkstra(grid);
        return ProcessQueries(queries, grid.Length * grid[0].Length, thresholdForMax);
    }
}