CODEWITHSUNDEEP
algorithmmatrixfortran
theenigma017
theenigma017

Reputation: 123

Simple way to find all paths from top row of a matrix to bottom row

Given a matrix A how will you find the number of all possible paths from row 1 to last row provided each '1' can connect with 3 elements adjacent to it in the row below (except for the edge 1's if any, they connect with 2 obviously).

I am looking for ways to implement this without using complex language-specific libraries or functions.

I'm using fortran95 and have tried for hours but still couldn't get all the paths.

A =

 0 1 0 1
 1 1 1 0
 1 0 1 0
 0 1 0 1

Upvotes: 0

Views: 1163

Answers (2)

user5713492
user5713492

Reputation: 974

The problem with the depth-first search for this problem is that it is O(3ⁿm) in the worst case because it traverses all possible paths. breadth-first search can be more efficient because it always uses roughly 3mn steps to generate all possible arcs of the graph only once, unless the array A is very sparse. Example of both, building on @Ekesh Kumar's pseudocode for the depth-first search:

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

Upvotes: 4

Ekesh Kumar
Ekesh Kumar

Reputation: 525

You can use a slight modification of the floodfill algorithm to solve this problem. Essentially, we are treating the two-dimensional grid as an implicit graph in which each unit square is a vertex, and two vertices are connected provided that one of the vertices is directly above or diagonally above the other vertex. Unfortunately, I am not familiar with Fortran, but here is some C++ code mixed in with some pseudocode that might help you. I will leave the specific implementation details to you.

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) 
}

Upvotes: 4

Related Questions