问查找矩阵从顶行到底行的所有路径的简单方法

EN

int count_paths(vector<vector<int>> grid) {
   int sum = 0;
   for (int i = 0; i < number of columns; i++) {
      sum += floodfill(0, i);
   }
   return sum;
}

int floodfill(int row, int column) {
   if (row, column) is out of bounds, return 0.
   if the value in the grid at (row, column) is 0, return 0.
   if we are in the last row, return 1. 

   return  floodfill(row + 1, column) + floodfill(row + 1, column + 1) + 
           floodfill(row + 1, column - 1) 
}

module functions
   implicit none
   contains
      recursive function depth_first(A,i,j) result(r)
         logical, intent(in) :: A(:,:) ! The map
         integer, intent(in) :: i      ! Row
         integer, intent(in) :: j      ! Column
         integer r                     ! Result variable
         if(j < 1 .OR. j > size(A,2)) then
            r = 0
         else if(.NOT. A(i,j)) then
            r = 0
         else if(i == size(A,1)) then
            r = 1
         else
            r = depth_first(A,i+1,j-1)+depth_first(A,i+1,j)+depth_first(A,i+1,j+1)
         end if
      end function depth_first

      function breadth_first(A)
         logical, intent(in) :: A(:,:) ! The map
         integer breadth_first         ! Result variable
         integer row(size(A,2))        ! Number of path to elements of current row
         integer i                     ! Current row
         row = merge(1,0,A(1,:))
         do i = 2, size(A,1)
            row = merge(eoshift(row,-1)+row+eoshift(row,1),0,A(i,:))
         end do
         breadth_first = sum(row)
      end function breadth_first
end module functions

program paths
   use functions
   implicit none
   integer, parameter :: m = 4 ! Number of rows
   integer, parameter :: n = 4 ! Number of columns
   ! Using a LOGICAL array is more 'Fortranny' :)
   logical :: A(m,n) = reshape([ &
      0, 1, 0, 1, &
      1, 1, 1, 0, &
      1, 0, 1, 0, &
      0, 1, 0, 1], &
      [m,n], order = [2,1]) == 1
   integer j                  ! Current column in first row
   write(*,'(*(g0))') 'Results of depth-first search: paths = ',sum([(depth_first(A,1,j),j=1,n)])
   write(*,'(*(g0))') 'Results of breadth-first search: paths = ',breadth_first(A)
end program paths