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

Answer:

Java code:

import java.util.*;

//class name

Public class northEast

{

//constructor

northEast()

{

}

//main method

public static void main(String[] args)

{

declarations

String paths;

//instance for the class

northEast ne=new northEast();

//getting the user inputs

Scanner inputR = new Scanner(paths);

Scanner inputE = new Scanner(paths);

int gridSize = inputR.nextInt();

int gt=inputE.nextInt();

boolean[][] gridVal = new boolean[gridSize][gridSize];

ne.norEast(inputR,inputE,paths);

gridVal.norEast(inputR,inputE,paths);

}

//method to calculate the northeast path

public static int norEast( int rowsV, int colsV, String pathV)

{

   if( rowsV == 0 && colsV == 0 )

   {

      System.out.println(pathV);

      return 1;

   }

   int npats1 = 0, wpaths1 = 0;

   if( rowsV != 0 )

      npaths1 = norEast( rowsV-1, colsV, pathV+"N" );

   if( colsV != 0 )

      wpaths1 = norEast( rowsV, colsV-1, pathV+"E" );

   return npaths + wpaths;

}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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