//Only the solution of third problem is being provided. //This is along similar lines to one of the practice problem on grid. //We compute the number of paths to go from origin to cheese //and square it to find all possible shortest routes for //the complete journey : origin->cheese->origin. //The logic is that for each path taken from origin to cheese //I can take any path from cheese to origin to complete //the journey and due to symmetry, thenumber of paths from //origin to cheese is the same as the number of paths from //cheese to origin. class Routes { public static long paths_to_cheese(int rights, int ups) { if(ups==0) return 1; else { if(rights==0) return 1; else return (paths_to_cheese(rights-1,ups) + paths_to_cheese(rights,ups-1)); } } public static long count_shortest_routes(int m, int n) { long num_of_shortest_paths = paths_to_cheese(m,n); return (num_of_shortest_paths * num_of_shortest_paths); } public static void main(String args[]) { int m = Integer.parseInt(args[0]); int n = Integer.parseInt(args[1]); long num_shortest_routes; num_shortest_routes = count_shortest_routes(m, n); System.out.println("The number of shortest routes for +"+m+" by "+n+" grid are "+num_shortest_routes); } }