CareerCup

int numOfPaths(int A[4][4], int n)
{
	int B[4][4];
	// if starting point blocked then no path is there to reach right down
	if( A[0][0] == 0)
	{
		return 0;
	}
	else
	{
		int i,j;
		for(i=0; i<n; i++)
		{
			if( A[0][i] == 0 )
				break; // exit from the for loop, and set remaining elements the first row set to ZERO
			B[0][i] = A[0][i];
		}
		
		while(i<n)
			B[0][i++] = 0; 

		for(i=1; i<n; i++)
		{
			if( A[i][0] == 0 )
				break;// exit from the for loop, and set remaining elements in the first column set to ZERO
			B[i][0] = A[i][0];
		}
		while(i<n)
			B[i++][0] = 0;

		for(i=1; i<n; i++)
			for(j=1; j<n; j++)
				if( A[i][j] == 0)
					B[i][j] = 0;
				else
					B[i][j] = B[i-1][j] + B[i][j-1];
		return B[n-1][n-1];
	}	
}

int main()
{
	int A[4][4] = {{1,1,1,1},
	{0,1,0,1},
	{0,1,1,0},
	{1,1,1,1}};
	
	int paths = numOfPaths(A, 4);
	printf("\n numofpaths = %d\n", paths);
	return 0;
}

Correction: for 3X3 matrix, the total number of paths is 4!/2!2! = 6.
Its same as arrangements of 2 DOWN and 2 RIGHT arrows.

I may be spoiling the fun here.
For part 1, the total number of ways in which one can travel from top-left to bottom-right in (M+1)x(N+1) matrix is equivalent to arrangement of M DOWN arrows and N RIGHT arrows. The formula for which is (M+N)!/M!N!.
For blocked case: suppose we start at (1,1), end at (M,N) and (i,j) is blocked. If we have p TOTAL paths from (1,1) to (i,j) and q UNBLOCKED paths from (i,j) to (m,n) then the unique paths passing through (i,j) is p*q. These we should ignore. Similarly, we ignore for other blocked elements. That there is no overlapping among these ignored paths is ensured by q.
Let me know if this is still not clear, for its somewhat difficult to explain. Also, let me know if you see any error in the approach.
Below is the implementation. Code is non-optimal (didn't use Dynamic Programming). Also space complexity can be improved.

#include<stdio.h>

#define FREE 0
#define BLOCKED 1

/* static allocation */
int M[100][100];

/* Matrix entry */
typedef struct {
    int r, c;
} entry;

int factorial(int n) {
    int nfact;
    for(nfact=1; n>0; n--)
        nfact*=n;
    return nfact;
}

/* ignoring blockages, total number of paths */
int free_path(entry s, entry d) {
    int total;
    int m, n;
    m = d.r - s.r;
    n = d.c - s.c;
    return factorial(m+n) / (factorial(m) * factorial(n));
}

/* considering blockages, total number of paths */
int available_path(entry s, entry d) {
    entry temp;
    int total = free_path(s, d);
    int r, c;
    for(r=s.r; r<=d.r; r++) {
        for(c=s.c; c<=d.c; c++) {
            /* ignore if first entry is blocked (bad workaround)
               check if current entry is blocked, if so ignore all paths
               passing through this entry */
            if(!(r==s.r && c==s.c) && M[r][c] == BLOCKED) {
                temp.r = r;
                temp.c = c;
                total -= (free_path(s, temp) * available_path(temp, d));
            }
        }
    }
    return total;
}

/* initialize the matrix with given number of rows and columns */
void initialize(int m, int n) {
    int r, c;
    for(r=0; r<m; r++) {
        for(c=0; c<n; c++) {
            M[r][c] = FREE;
        }
    }
}

/* block a specific entry */
void block(int r, int c) {
    M[r][c] = BLOCKED;
}

int main() {
    entry start, end;
    int m, n;
    m = 5;
    n = 4;
    
    // create an MxN matrix
    initialize(m, n);
    
    start.r = 0;
    start.c = 0;
    end.r = m-1;
    end.c = n-1;
    
    // block a set of entries
    block(1, 1);
    block(2, 1);
    
    printf("Count=%d\n", available_path(start, end));
    return 0;
}

I give it a try by using DP.

I declare 2D array for mXn matrix as D[m+1][n+1] then in this case we travel from cell D[0][0] to cell D[m][n]. we can see the the recurrence relationship is D[i][j] = D[i+1][j] + D[i][j+1].

We initialize our D matrix to have value 1 at D[m][n+1] (1 cell right to finish cell D[m][n]). Block path is set to value 0 means that there is no path to travel to 4 neighbor cells (let's say Block indices is (bi, bj), then D[bi][bj] = 0 which will not increase calculation of (Down Neighbor) D[bi+1][bj], (Up Neighbor) D[bi-1][bj] and so on ..)

Then we calculate the recurrence relationship for all i(s), j(s) in bottom up manner from (m->0), (n->0).

(I have set initialized value as -1 to be determined that cells will be calculated later (They are not blocked cells))

class UniquePath {
	public:
		UniquePath(int, int);
		~UniquePath();
		void init();
		void blockPath(int, int);
		void calculatePath();
		void display();
	private:
		vector< vector<int> > D;
		int M;
		int N;
}; 

UniquePath::UniquePath(int m, int n) {
	M = m+1;
	N = n+1;
}
UniquePath::~UniquePath() {
}

void UniquePath::init() {
	D.resize(M);
	for (int i = 0; i < M; ++i) {
		D[i].resize(N);
	}	
	for (int i = 0 ; i < M; ++i) {
		for(int j =0 ; j <  N; ++j) {
			D[i][j] = -1;
			if (i == (M-1)) D[i][j] = 0;
			if (j == (N-1)) D[i][j] = 0;
		}
	}
	//set first path
	D[M-2][N-1] = 1;
}

void UniquePath::blockPath(int r, int c) {
	for (int i = 0; i < M; ++i) {
		for(int j = 0; j < N; ++j) {
			if (i == r && j == c) D[i][j] = 0;
		}
	}
}

void UniquePath::display() {
	for (int i = 0; i < M; ++i) {
		for(int j = 0; j < N; ++j) {
			cout << D[i][j] << "\t";
		}
		cout << endl;
	}
}

void UniquePath::calculatePath() {
	for (int i = M-1; i > -1; --i) {
		for (int j = N-1; j > -1; --j) {
			if (D[i][j] == -1) D[i][j] = D[i+1][j] + D[i][j+1];
		}
	}
}

int main () {
	UniquePath up(3,7);
	up.init();
	up.blockPath(1,1);
	up.blockPath(1,3);
	//.... so on
	up.calculatePath();
	up.display();
}

public class FindNumberOfPathsMxMmatrix {	
	
	static public int findNumPaths(int x, int y, char[][] m) {		
		if (x == m[0].length - 1 && y == m.length - 1 && m[y][x] != 'x') 
			return 1;		
		if (x > m[0].length - 1 || y > m.length - 1 || m[y][x] == 'x') 
			return 0;			
		return findNumPaths(x, y + 1, m) + findNumPaths(x + 1, y, m);				
	}

	public static void main(String[] args) {		
		char[][] m = 
		  { { 'o', 'o', 'o'}, 
			{ 'o', 'x', 'o'}, 
			{ 'o', 'o', 'o'} };		
		
		int result = findNumPaths(0, 0, m);
		System.out.println(result);
	}
}

<pre lang="" line="1" title="CodeMonkey71852" class="run-this">
#define M 1000
#define N 1000

int num_paths(int i, int j);

int main(){
int x = num_paths(1, 1);
printf("Number of paths = %d", x);
return EXIT_SUCCESS;
}

int num_paths(int i, int j) {
if((i == M) && (j == N)) {
return 1;
}
else if((i > M) || (j > N)) {
return 0;
}
else {
return num_paths(i+1, j) + num_paths(i, j+1);
}
}

</pre>

a[0][0]=0;


a[0][j]=a[0][j-1]+1;
a[i][0]=a[i-1][0]+1;

i and j are >1
a[i][j]=a[i-1][j]+a[i][j-1];

compute till i==m and j==n

correct second and third line with this a[0][j]=1 for j>0 and a[i][0]=1 for i>0

correct second and third line with this a[0][j]=1 for j>0 and a[i][0]=1 for i>0

#include<stdio.h>
#include<conio.h>
char m[4][4] = 
		  { { 'x', 'x','x','x'}, 
			{ 'x', 'x','o','x'},
            { 'x', 'x','x','o'}, 
			{ 'x', 'x','x','x'}};
int row=4,col=4; 
int noofwayspsbl(int p,int q)
{
if (p>row-1 || q>col-1 || m[p][q]=='o') return 0;
if (p==row-1 && q==col-1 && m[p][q]=='x') return 1;
return (noofwayspsbl(p+1,q)) + (noofwayspsbl(p,q+1));
}
    
int main()
{
   printf("\n Possible no of paths is = %d",noofwayspsbl(0,0));
    getch();
    return 0;
}

#include<stdio.h>
#include<conio.h>
char m[4][4] = 
		  { { 'x', 'x','x','x'}, 
			{ 'x', 'x','o','x'},
            { 'x', 'x','x','o'}, 
			{ 'x', 'x','x','x'}};
int row=4,col=4; 
int noofwayspsbl(int p,int q)
{
if (p>row-1 || q>col-1 || m[p][q]=='o') return 0;
if (p==row-1 && q==col-1 && m[p][q]=='x') return 1;
return (noofwayspsbl(p+1,q)) + (noofwayspsbl(p,q+1));
}
    
int main()
{
   printf("\n Possible no of paths is = %d",noofwayspsbl(0,0));
    getch();
    return 0;
}