
PROGRAM Path_Counter
!-----------------------------------------------------------------------
! Program to count "northeasterly" paths from a given starting point
! in a network of streets to a specified ending point.
!   StartRow, StartColumn : coordinates of starting point
!   EndRow, EndColumn     : coordinates of ending point
!   Number_of_Paths       : recursive function to count paths
!
! Input:  StartRow, StartColumn, EndRow, EndColumn
! Output: Number of northeast paths
!-----------------------------------------------------------------------

  IMPLICIT NONE
  INTEGER :: StartRow, StartColumn, EndRow, EndColumn

  PRINT *, "Enter the starting coordinates (row then column):"
  READ *, StartRow, StartColumn
  PRINT *,  "Enter the ending coordinates (row then column):"
  READ *, EndRow, EndColumn

  PRINT *, "There are", &
            Number_of_Paths(EndRow - StartRow, &
                            EndColumn - StartColumn),  " paths"
 STOP

CONTAINS

  ! Number_of_Paths ----------------------------------------------------
  ! A recursive function to calculate the number of northeasterly paths
  ! in a network of streets. Identifiers used are:
  !   Number_of_Rows,  Number_of_Columns : number of rows and
  !               columns from starting postion to ending position
  !   NUM_PATHS : number of paths
  !
  ! Accepts:  Number_of_Rows, Number_of_Columns
  ! Returns:  Num_Paths
  !---------------------------------------------------------------------
  
  RECURSIVE FUNCTION Number_of_Paths &
               (Number_of_Rows,  Number_of_Columns) RESULT (Num_Paths)
  
    INTEGER, INTENT(IN) :: Number_of_Rows, Number_of_Columns
    INTEGER :: Num_Paths
  
    IF ((Number_of_Rows == 0) .OR. (Number_of_Columns == 0)) THEN
       Num_Paths = 1
    ELSE
       Num_Paths = &
           Number_of_Paths(Number_of_Rows - 1, Number_of_Columns) &
         + Number_of_Paths(Number_of_Rows, Number_of_Columns - 1)
    END IF
    RETURN
  END FUNCTION Number_of_Paths
  

END PROGRAM Path_Counter