This is to find all possible paths starting from left top corner of matrix to right bottom corner
But we have constrain on this. You can only move Right or bottom and we also have blocking, Here blocking means 0 and path means 1. You can move to particular right or bottom if we have 1 on this box.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
int a[][] = new int[][]{ { 1, 1, 1, 1 }, { 0, 1, 0, 1 }, { 0, 1, 1, 0 }, { 1, 1, 1, 1 } }; |
As per above matrix, We can get two different paths from Top Left to Bottom Right.
Algorithm
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
package com.omt.learn.algo; public class NumberOfPath { public static void main(String[] args) throws Exception { int a[][] = new int[][]{ { 1, 1, 1, 1 }, { 0, 1, 0, 1 }, { 0, 1, 1, 0 }, { 1, 1, 1, 1 } }; System.out.println(numberOfPaths(a)); } private static int numberOfPaths(int[][] a) { int m = a.length; int n = a[0].length; return numberOfPaths(a, 0, 0, m, n); } private static int numberOfPaths(int[][] a, int i, int j, int m, int n) { if (i < m && j < n) { if (a[i][j] == 1) { if (i == m - 1 && j == n - 1) { return 1; } else { return numberOfPaths(a, i, j + 1, m, n) + numberOfPaths(a, i + 1, j, m, n); } } else { return 0; } } return 0; } } |