Advertisement
gelita

lattice paths with x/y variables for clarity

Feb 15th, 2020
211
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 5 1.15 KB | None | 0 0
  1. import java.io.*;
  2.  
  3. /*input: int m, int n->  integers of a lattice where m = height and n = width of lattice,
  4.   output: number or ways/paths to get from 0,0 to bottom right
  5.   example: input: 2,3
  6.         output :10
  7.   (2 x 3 lattice of squares)
  8.    *            0  __1 _2 __3
  9.    *            1 |__ |__|__|
  10.    *            2 |__ |__|__|  
  11.    *
  12.    * ***work this going from top down--from input to 0,0. when    
  13.    *   0 is reached that is a base case
  14.    
  15.    * n+ m = number of steps total
  16.    (n+m)!/ (n!m!) is the total paths possible
  17.    ex: (2,3) --> 5!/3!2!--> 5*4*3*2*1/3*2*1*2*1
  18.    --> 5*2= 10 possible paths
  19.   */
  20. class MyCode {
  21.  
  22.   public static void main(String[] args){
  23.     int x = 10;
  24.     int y = 10;
  25.     System.out.println(countPaths(x,y));
  26.    
  27.   }
  28.  
  29.   public static int countPaths(int x, int y){
  30.     if(x == 0 && y == 0){
  31.       return 1; //only 1 way to start at start
  32.     }
  33.     if(x == -1 || y == -1){
  34.       return 0; //not possible to be out of bounds
  35.     }
  36.    
  37.     int countLeft = countPaths(x, y-1);// width/y-axis chgs
  38.     int countUp = countPaths(x-1, y); // height/x-axis chgs
  39.     return countUp + countLeft;
  40.   }
  41. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement