Consider a network of streets laid out in a rectangular grid for example: In a n

Question

Consider a network of streets laid out in a rectangular grid for example:

In a northeast path from one point in the grid to another, one may walk only to the north (up) and to the east (right). For example, there are 4 northeast paths from A to B in the preceding grid.

Write a java program that uses a recursive method to count the number of the northeast paths from one point to another in a rectangular grid. Also, output the actual paths taken

In this classic example, one needs to establish a set order of examination, say visit one's north and then one's east neighbors.

Then, one simply recurses north until one falls off of the grid. Recursion "automatically" takes care of backtracking to a legal grid point and then recursing to the east.

By restricting travel to only these two directions, one need not worry about creating cycles, and thus infinite recursion.

Has to be in Java

Explanation / Answer

<code>

import java.util.Scanner;

class main {
   public static void main(String[]args){
       Scanner in = new Scanner(System.in);
       System.out.println("Enter the starting point:");
       int x1 = in.nextInt();
       int y1 = in.nextInt();
       System.out.println("Enter the end point:");
       int x2 = in.nextInt();
       int y2 = in.nextInt();
       String str = "";
       printPath(x1,y1,x2,y2,str);
       in.close();
   }

   private static void printPath(int x1, int y1, int x2, int y2, String str) {
       // TODO Auto-generated method stub
       if (x1 == x2 && y1==y2){
           System.out.println(str);
           return;
       }
       String nstr = str+"E";
      
       if (x1 < x2){
           printPath(x1+1, y1, x2, y2, nstr);
       }

       nstr = str+"N";
       if(y1 < y2){
           printPath(x1, y1+1, x2, y2, nstr);
       }
   }
}

</code>

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.