Untitled

mail@pastecode.io avatar
unknown
plain_text
a month ago
2.3 kB
3
Indexable
Never
import java.util.Arrays;

public class MinCostPath {

    public static int minCostPath(int[][] grid) {
        int N = grid.length;
        int M = grid[0].length;

        // Initialize dp table
        int[][] dp = new int[N][M];
        for (int[] row : dp) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }
        dp[0][0] = (grid[0][0] >= 0) ? grid[0][0] : 0;

        // Fill dp table
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < M; ++j) {
                if (i == 0 && j == 0)
                    continue;

                if (grid[i][j] < 0) {
                    // Handle movement restrictions based on cell value
                    if (grid[i][j] == -1) {
                        // No downward movement
                        if (j > 0 && dp[i][j-1] != Integer.MAX_VALUE)
                            dp[i][j] = dp[i][j-1];
                    } else if (grid[i][j] == -2) {
                        // No rightward movement
                        if (i > 0 && dp[i-1][j] != Integer.MAX_VALUE)
                            dp[i][j] = dp[i-1][j];
                    } else if (grid[i][j] == -3) {
                        // No movement allowed from this cell
                        dp[i][j] = Integer.MAX_VALUE;
                    }
                } else {
                    // Regular movement
                    if (i > 0 && dp[i-1][j] != Integer.MAX_VALUE)
                        dp[i][j] = Math.min(dp[i][j], dp[i-1][j] + grid[i][j]); // Upward movement
                    if (j > 0 && dp[i][j-1] != Integer.MAX_VALUE)
                        dp[i][j] = Math.min(dp[i][j], dp[i][j-1] + grid[i][j]); // Leftward movement
                }
            }
        }

        // Check if the destination is reachable
        if (dp[N-1][M-1] == Integer.MAX_VALUE)
            return -1; // No Path
        else
            return dp[N-1][M-1];
    }

    public static void main(String[] args) {
        int[][] grid = {
            {1, 2, 4},
            {3, -3, 2},
            {2, 6, 0}
        };

        int result = minCostPath(grid);

        if (result == -1)
            System.out.println("No Path.");
        else
            System.out.println("Minimum cost path sum: " + result);
    }
}
Leave a Comment