Untitled
unknown
plain_text
a year ago
2.3 kB
6
Indexable
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); } }
Editor is loading...
Leave a Comment