1#include <stdio.h>
2#include <limits.h>
3#include <stdlib.h>
4#include <stdbool.h>
5
6#define MAX 100000
7
8typedef struct {
9    int x, y, priority;
10} Node;
11
12Node queue[MAX];
13int front = 0, rear = -1;
14
15void enqueue(Node n) {
16    queue[++rear] = n;
17}
18
19Node dequeue() {
20    return queue[front++];
21}
22
23bool isEmpty() {
24    return front > rear;
25}
26
27int minimumObstacles(int** grid, int gridSize, int* gridColSize) {
28    int m = gridSize, n = gridColSize[0];
29    int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
30    int dist[m][n];
31
32    for (int i = 0; i < m; ++i) {
33        for (int j = 0; j < n; ++j) {
34            dist[i][j] = INT_MAX;
35        }
36    }
37
38    dist[0][0] = 0;
39    enqueue((Node){0, 0, 0});
40
41    while (!isEmpty()) {
42        Node node = dequeue();
43        int x = node.x, y = node.y;
44
45        for (int i = 0; i < 4; ++i) {
46            int nx = x + directions[i][0];
47            int ny = y + directions[i][1];
48
49            if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
50                int cost = dist[x][y] + grid[nx][ny];
51                if (cost < dist[nx][ny]) {
52                    dist[nx][ny] = cost;
53                    Node newNode = {nx, ny, cost};
54                    if (grid[nx][ny] == 0) {
55                        queue[--front] = newNode;
56                    } else {
57                        enqueue(newNode);
58                    }
59                }
60            }
61        }
62    }
63    return dist[m - 1][n - 1];
64}

1using System;
2using System.Collections.Generic;

public class MinimumObstaclesDP {
    public int MinimumObstaclesDPMethod(int[][] grid) {
        int m = grid.Length, n = grid[0].Length;
        int[][] dp = new int[m][];
        for (int i = 0; i < m; i++) {
            dp[i] = new int[n];
            Array.Fill(dp[i], int.MaxValue);
        }

        var deque = new LinkedList<(int, int)>();
        dp[0][0] = 0;
        deque.AddFirst((0, 0));

        int[][] directions = { new[] {0, 1}, new[] {1, 0}, new[] {0, -1}, new[] {-1, 0} };

        while (deque.Count > 0) {
            var current = deque.First.Value;
            deque.RemoveFirst();
            int x = current.Item1, y = current.Item2;

            foreach (var dir in directions) {
                int nx = x + dir[0], ny = y + dir[1];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
                    int cost = dp[x][y] + grid[nx][ny];
                    if (cost < dp[nx][ny]) {
                        dp[nx][ny] = cost;
                        if (grid[nx][ny] == 0) {
                            deque.AddFirst((nx, ny));
                        } else {
                            deque.AddLast((nx, ny));
                        }
                    }
                }
            }
        }

        return dp[m - 1][n - 1];
    }
}