Advertisement
exmkg

GridPaths

Feb 11th, 2025
110
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.47 KB | None | 0 0
  1. import java.util.Scanner;
  2.  
  3. public class GridPaths {
  4.  
  5.     public static void main(String[] args) {
  6.         Scanner scanner = new Scanner(System.in);
  7.  
  8.         // Read the size of the grid (n)
  9.         int n = scanner.nextInt();
  10.         scanner.nextLine(); // Consume the newline character
  11.  
  12.         // Read the grid as a 2D char array
  13.         char[][] grid = new char[n][n];
  14.         for (int i = 0; i < n; i++) {
  15.             String row = scanner.nextLine();
  16.             grid[i] = row.toCharArray();
  17.         }
  18.  
  19.         // dp[i][j] stores the number of paths from (0, 0) to (i, j)
  20.         int[][] dp = new int[n][n];
  21.  
  22.         // Modulo value to prevent integer overflow
  23.         int MOD = 1000000007;
  24.  
  25.         // Base case: If the starting cell is a trap, there are no paths
  26.         if (grid[0][0] == '*') {
  27.             System.out.println(0);
  28.             scanner.close();
  29.             return;
  30.         }
  31.  
  32.         // Initialize the starting cell (top-left) to 1 (one path to itself)
  33.         dp[0][0] = 1;
  34.  
  35.         // Fill the first row.  We can only reach (0, j) if all cells to its left are free.
  36.         for (int j = 1; j < n; j++) {
  37.             if (grid[0][j] == '.') {
  38.                 dp[0][j] = dp[0][j - 1]; // Number of paths is same as the cell to the left
  39.             } else {
  40.                 dp[0][j] = 0; // Trap, no paths
  41.             }
  42.         }
  43.  
  44.         // Fill the first column. We can only reach (i, 0) if all cells above it are free.
  45.         for (int i = 1; i < n; i++) {
  46.             if (grid[i][0] == '.') {
  47.                 dp[i][0] = dp[i - 1][0]; // Number of paths is same as the cell above
  48.             } else {
  49.                 dp[i][0] = 0; // Trap, no paths
  50.             }
  51.         }
  52.  
  53.  
  54.         // Iterate through the rest of the grid (excluding first row and column)
  55.         for (int i = 1; i < n; i++) {
  56.             for (int j = 1; j < n; j++) {
  57.                 // If the current cell is a trap, there are no paths to it
  58.                 if (grid[i][j] == '*') {
  59.                     dp[i][j] = 0;
  60.                 } else {
  61.                     // The number of paths to (i, j) is the sum of paths from the cell above (i-1, j)
  62.                     // and the cell to the left (i, j-1), modulo MOD.
  63.                     dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % MOD;
  64.                 }
  65.             }
  66.         }
  67.  
  68.         // The result is stored in dp[n-1][n-1] (bottom-right cell)
  69.         System.out.println(dp[n - 1][n - 1]);
  70.  
  71.         scanner.close();
  72.     }
  73. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement