CareerCup

First place question should be "Given if the element is 1 we can move Right or down, if it is 0 we can only proceed downward".
Then find the working code.......
Plz give any comment....

#include<stdio.h>

#define ROW 3
#define COL 3
#define MAX ROW*COL

int NextDistance(int, int);

int arr[3][3] = {1, 1, 0, 0, 0, 0, 1, 0, 0};

int main(void)
{
   int i, j, dist;
   printf("\nOrigina Array......\n");
   for(i=0; i<ROW; i++)
   {
        for(j=0; j<COL; j++)
           printf("\t%d", arr[i][j]);
        printf("\n");
   }

   dist = NextDistance(0, 0);
   if(dist < MAX)
        printf("\nShortest Distance : %d\n\n", dist);
   else
        printf("\nThere is no path exist from start element to end element....\n\n");

   return 0;
}

int NextDistance(int i, int j)
{
    int slen=MAX, slen1=MAX, slen2=MAX;
    if(i==ROW-1 && j==COL-1)
        return 0;
    else if(i==ROW-1 && arr[i][j]==0)
        return MAX;
    else if(arr[i][j] == 0)
    {
        if(i < ROW-1)
            slen = 1 + NextDistance(i+1, j);
    }
    else
    {
        if(j < COL-1)
            slen1 = 1 + NextDistance(i, j+1);
        if(i < ROW-1)
            slen2 = 1 + NextDistance(i+1, j);
        slen = slen1<slen2 ? slen1 : slen2;
    }
    return slen;
}

flood fill algorithm

for an array of size MxN, does the first element mean element at 0,0 and last element mean the element at M-1,N-1 (assuming 0 based indexing) ?

shortest distance between the first and the last element in a two dimension:

Case 1: first element = a[0][0] & last element a[M][N]
Sol: you can never move from a[0][0] to a[M][N] with only possible action left and down. Right move is required unless left move from a[0][0] is not a[0][N]

Case 2: first element = a[0][0] & last element a[M][index] (bottom row)
Sol: no matter what matrix is given made up with o and 1. ans will always M down moves.

Case 3: first element = a[0][0] & last element a[M][N] (right most column) and we have move down or right for each 1
Sol: when ever you got 1 go right and down for 0...once reached rightmost column go down for all elements (0 or 1)

There seems to be a problem with the mechanics of the question.
- You want to start at (0,0) and go to (m-1,n-1) in a m by n grid.
- As per your question, on seeing a 1 you can move left or down and on seeing a 0 you can move only down.
- The problem with this is that you are never able to move right and you may never reach (m-1, n-1).

So , the second part of your question ought to be something like this :

Given, if the element is 1, we can move LEFT or DOWN, if it is 0 we can move RIGHT or UPWARDS.

1.Go right if the value of the array[i][j] is 1 and j!=N-1, if j is N-1 then move down and you are done.

2. go right if array[i][j] is 1 ,and go left if array[i][j]=0
3. Loop till i<M and j<N

#include<stdio.h>
int findPath(int arr[][4],int posx, int posy, int maxx, int maxy)
{
	int pathFound = 0;
	printf("x:%d and y:%d\n",posx,posy);
	if(posx < maxx && posy < maxy-1)
	{
		if(arr[posx][posy] == 1)
		{
			pathFound = findPath(arr,posx,posy+1,maxx,maxy);
		}
		if( pathFound == 0)
		{
			pathFound = findPath(arr,posx+1,posy,maxx,maxy);
		}
	}
	else if(posy == maxx-1)
	{
		pathFound = 1;
	}
	return pathFound;
}
int main()
{
	int arr[4][4] = {{0,0,0,0},{0,0,0,0},{0,0,0,0},{0,1,1,0}};
	printf("%d",findPath(arr,0,0,4,4));
}

i think this works fine

Consider the matrix to represent a graph where zero means presence of an edge and one implies absence of an edge. Then run BFS to find the shortest path between given indices i, and j.

Create a Graph from the given conditions, where each cell in the Matrix is a Node. Give each cell a number and when value is 0 it connects to two other cell through graph edge. When value is 1, it connects to only one cell.

After that run Graph Shortest path algorithm with same weight for each edge.

yr only in few cases we can solve this because in most of the cases you will come in the last row with 0 and you can't move down after that ..
is this questions is correct or rahul is correct

Since each move is either right or down.
Total moves required = (N-1)DOWN MOVES + (M-1) right moves == N+M-2 (always)
so problem reduces to:

if(there_is_a_path)return N+M-2;
else INT_MAX;