CareerCup

We can solve the above problem using recursion with backtracking.

We start by moving from the bottom-right cell that is (m-1,n-1). We can move either left or top from each cell. Recursively call the findPath function with left cell and top cell. If you encounter a 0 at a cell position, discard that path. When we reach the (0,0) cell, increment the count variable.

Keep a count variable that keeps track of all the possible path.

Code :

public class Practice67 {
	public static void main(String[] args){
		int arr[][] = {{1,1,1,1},
					   {1,0,0,1},
					   {1,0,0,1},
					   {1,1,1,1}};
		
		System.out.println(findPaths(arr,3,3,0));		
		}
	public static int findPaths(int[][] arr,int m,int n,int count){
		
		if(0 == m && 0 == n){
			count++;
			return count;
		}
		if(n > 0 && arr[m][n-1] != 0){
			count = findPaths(arr,m,n-1,count);
		}
		if(m>0 && arr[m-1][n] != 0){
			count = findPaths(arr,m-1,n,count);
		}
		return count;
	}
}

//Using DP

int a[m][n];
int paths[m][n] = {0};

for(i=0; i<m; i++) {
	for(j=0; j<n; j++) {
		if(i==0 && j==0) {
			paths[i][j] = 1;
			continue;
		}
		if(a[i][j] == 0)
			paths[i][j] = 0;
		else
			paths[i][j] = (i-1 >=0?paths[i-1][j]:0) + (j-1>=0?paths[i][j-1]:0);
	}
}

printf("Number of paths = %d\n", paths[m-1][n-1]);

I would think that you can do BFS.

Mark nodes visited with a negative value, starting with -1.
When two paths meet the same point make it count for path 1 + path 2. I.e. -1 + -1 = -2 etc.
Return the value when you reach end.

How about this:

To make life easy set A(M,j) = 0 and A(i,N) = 0;

for (i = M - 1; i >= 0; i--) {
    for (j = N - 1; j >= 0; j--) {
        if (A(i,j) == 0)
            F(i,j) = 0;
        else 
            F(i,j) = F(i+1,j) * A(i+1,j) + F(i,j+1) * A(i,j+1);
    }
}

numberOfPaths = F(0,0);

Convert the matrix to a DAG: each '1' cell makes a vertex, which is connected to its right/down neighbors (if exist). There are no back edges (cycles), because we're not allowed to go up or left - hence we have a DAG. This is good, because there are polynomial algorithms for finding all paths between two nodes in a DAG:
the idea resembles DP, where in each step we build on top of the previous ones. we'll compute the number of distinct paths from a given node to the target node by summing up the paths counters of its descendants. we start from the nodes directly connected with the target node and go backwards till we get to the source. the easiest way for verifying that we only process a node after all its children are processed is to run first a topological sort and then process the nodes in a topological reverse order.

public class FindPath {

	/**
	 * @param args
	 */
	int m=5;
	int n=5;
	static int count=0;
	
	public static void main(String[] args) {
		
		FindPath fp=new FindPath();
		
		int arr[][]=new int[][]{{1,0,1,0,0},{1,0,0,1,1},{1,1,1,1,1},{0,1,1,1,1},{1,1,0,0,1}};
		fp.findPaths(arr,0,0,"");
		System.out.println("Total Path : "+count);
	}

	private void findPaths(int[][] arr, int i, int j, String path) {
		
		path=path+" ("+i+","+j+")";
		if(i==(m-1) && j==(n-1))
		{
			System.out.println(path);
			count++;
			return;
		}
		
		if(i<(m-1) && arr[i+1][j]==1)
		{			
			findPaths(arr, i+1, j, path);
		}
		if(j<(n-1) && arr[i][j+1]==1)
		{
			findPaths(arr, i, j+1, path);
		}
		
			
			return;
	}

}

public void PathArray()
{
int[,] ipmatrix = new int[4, 4] { { 1,1,0,0 }, { 1,1,1,0}, {0,1,1,0}, { 1,0,1,1} };
int rowlen=ipmatrix.GetLength(0);
int collen=ipmatrix.GetLength(1);
int count = 0;
count= wrapperpatharray(ipmatrix, 0, 0, rowlen, collen);

}

public int wrapperpatharray(int[,] ip,int i,int j, int rowlen, int collen)
{

if (i == rowlen - 1 && j == collen - 1)
{
Console.WriteLine("Pathfound");
return 1;
}
if (i > rowlen - 1 || j > collen - 1)
return 0;
if (ip[i, j] == 0)
return 0;

return( wrapperpatharray(ip, i, j + 1, rowlen, collen)+
wrapperpatharray(ip, i + 1, j, rowlen, collen));

}

///
function numberOfPaths(arr) {

// Assume each row has the same number of arguments
var M = _array.length;
var N = _array[0].length;
var pathCount = 0;

var x = 0;
var y = 0;

findPath(arr, x, y, M, N);
console.log(pathCount + " paths found!");

function findPath(a, x, y, rows, cols) {

if (a[y][x]) {

// Check end condition
if (y == rows-1 && x == cols-1) {
pathCount++;
}
if (x+1 < cols) {

// Check right
findPath(a, x+1, y, rows, cols);
}
if (y+1 < rows) {

// Check down
findPath(a, x, y+1, rows, cols);
}
}
else {
console.log("Dead end ("+y+", "+x+")");
}
}
}
\\\

use DP...o(n2) solution

package test;

public class ArrayPath {

private int totalNumberOfPath = 0;

public int numberOfPaths(int[][] array) {
if (array[0].length == 0 || array.length == 0) {
return -1;
}
findPath(array,0,0);
return totalNumberOfPath;
}

private void findPath(int[][] array, int posX, int posY) {
if (posX == array[0].length - 1 && posY == array.length -1) {
totalNumberOfPath++;
return;
}
if (posX+1 < array[0].length && array[posY][posX+1] == 1) {
findPath(array, posX+1, posY);
}
if (posY+1 < array.length && array[posY+1][posX] == 1) {
findPath(array, posX, posY+1);
}
return;
}

public static void main(String argv[]) {
ArrayPath arrayPath = new ArrayPath();
int[][] array = {{1, 1, 1, 1},
{1, 1, 1, 1},
{1, 0, 1, 1}};

System.out.println(arrayPath.numberOfPaths(array));
}
}

#include <stdio.h>

int count=0;
int maxrows = 10;
int maxcols = 10;
int M, N;

void DFS (int array[][10], int x, int y)
{
int r, c;

    /* process element at input row and column */

    if (array [x][y]==0 || x>M || y>N){
    /* no path forward; return */
        return;
    }
    if (x==M-1 && y==N-1){
        /* found path; increment count */
        count++;
        return;
    }
    /* recurse: to matrix starting from same row, next column */
    r = x;
    c = y +1;
    if (c < N-1) {
        DFS (array, r,c);
    } else {
        /* if last column - check to see  */
        /* if rest of rows in last column allow for a path */
        int tr = r;
        while ( tr <= M-1)  {
            if (array[tr][c] == 1) {
                tr++;
            }       
            else {
                return;
            }
        }
        /* reached last node - path exists! */
        count++;
    }
    /* recurse: to matrix starting from next row, same column */
    r = x+1;
    c = y;
    if (r < M-1) {
        DFS (array, r,c);
    } else {
        /* if last row - check to see  */
        /* if rest of columns in last row allow for a path */
        int tc = c;
        while ( tc <= N-1)  {
            if (array[r][tc] == 1) {
                tc++;
            } else {
                return;
            }
        }
        /* reached last node - path exists! */
        count++;
    }
}

int main () {
    int i, j;
        scanf("%d %d",&M,&N);
        int a[10][10] = {};
    int row, col;

        for(i=0;i<M;i++)
                for(j=0;j<N;j++)
                        scanf("%d", &a[i][j]);
        if ((M > maxrows) || (N > maxcols)) {
        printf("max of 10 rows and 10 cols allowed for input\n");
            return (-1);
        };
    /* print input matrix */
        for(row=0;row<M;row++) {
                for(col=0;col<N;col++){
                        printf("%d ",a[row][col]);
                }
                printf(" EOR\n");
        }
    DFS(a,0,0);
        printf("number of paths is %d\n", count);
        return 0;
}

Use the android app for Careercup

store/apps/details?id=com.andersoncouncil.careercup.ui