# Maximum Path length • ### Question

• This Program finds the maximum path from any position in a 2-D matrix.

We can either jump to the right  to a cell in the same row, provided that the number written in that cell is not smaller than the number written in the current cell.

OR

jump downward to a cell in the same column, provided that the number written in that cell is not greater than the number written in the current cell.

For example- In

```2 1 1
2 1 1has 3(1,1,1)
6 2 5 2
4 5 3 8
9 7 8 9
9 9 9 5 has 5(2,5,3,8,5).It can have other possible answer also.#include<stdio.h>
#include<conio.h>

#define m 500
#define n 500

int maximum(int,int,int,int);		//function prototype

int a[m][n], b[m], r, c, t, k=0, count = 1, max;		//global variables

int main()
{
int i,j;
scanf_s("%d",&t);		//entering number of tests

while(t--)
{
scanf_s("%d %d",&r,&c);		//entering rows and columns
for(i = 0;i < r; i++)
for(j = 0; j < c; j++)
scanf_s("%d",&a[i][j] );   //entering elements

for(i = 0; i < r; i++)		//making a[c], a[c], a[c]....a[r-1][c] infinitly negative
a[i][c] = -99999999;		//so that comparing with them always results false in the maximum function

for(j = 0; j < c; j++)		//making a[r], a[r], a[r]....a[r][c-1] infinitly positive
a[r][j] = 99999999;

for(i=0;i<r;i++)
{
for(j = 0; j < c; j++)
{
b[k] = maximum(r, c, i, j);	//calling function each time with new position
//eg. (0,0) , (0,1) to find all possible path lengths
count=1;		//resetting count=1 for next pass

k++;			//incrementing k to store next count
//value at next position in array
}
}
max = b;
for(i = 1; i < k; i++)	//finding maximum value among all the values of count stored in aarray b[k]
{
if( b[i] > max )
max = b[i];
}

printf("%d\n", max );		//printing maximum value

}
_getch();
return 0;
}
int maximum(int r, int c, int i, int j)
{
if( i < r && j < c )
{
if(a[i][j] <= a[i][j+1] && a[i][j] >= a[i+1][j] )		//if both conditions satisfies
{
count++;	//incrementing value of count
maximum(r, c, ++i, j);		//calling recursively with 1st possible path
maximum(r, c, i, ++j);     //calling recursively with 2nd possible path
}
else if( a[i][j] <= a[i][ j+1 ] )				//right move
{
count++;
j++;
maximum(r, c, i, j);
}
else if( a[i][j] >= a[ i + 1 ][j] )			//move down
{
count++;
i++;
maximum(r, c, i, j);
}
else if( a[i][j] > a[i][ j+1 ] && j < c )		//to compare with the next element in a row to which it does not
{												//satisfies the condition
int p = j + 1;
while(p < c && a[i][j] > a[i][p])			//eg. 6 2 5 2
{											//    4 5 3 8
if(a[i][j] <= a[i][ ++p ])				//    9 7 8 9
{										//    9 9 9 5
count++;							// 6 then 4 then 5(same row) then checking for 8 since it doesnt satisfy
maximum(r, c, i, p);				// condition for 3 and then for 5(same column of 8)
}
}
}
else if(a[i][j] < a[i+1][j] && i < r)			//to compare with the next element in a column to which it does not
{												//satisfies the condition
int p = i + 1;
while(p < r && a[i][j] < a[p][j])
{
if(a[i][j] >= a[ ++p ][j])
{
count++;
maximum(r, c, p, j);
}
}
}
else
{
b[k] = count;		//storing value of count in each pass in an array
return b[k];		//returning
}
}
}Problem is it shows correct output in Visual C++(3 and 5) but shows 0 as output in Dev-C++ and 1002 2003 as output for same input when compiled on ideone.com online compiler. I am not able to find why is this so?Hope you can help me.
```

Friday, September 28, 2012 5:03 PM

• `Problem is it shows correct output in Visual C++(3 and 5) but shows 0 as output in Dev-C++ and 1002 2003 as output for same input when compiled on ideone.com online compiler. I am not able to find why is this so?Hope you can help me. `

I don't know if it matters but you do not assign a[r][c] a value so it will remain 0 as implicitly initialized.

Do all three systems have the same size int?  I suggest using INT_MAX and INT_MIN for your boundary conditions (instead of 99...).

Do the other compilers have debuggers?  If so, you should be able to step through the code on each one and see where the difference occurs.  If not, add some debugging calls to printf at the top of each for loop as a "trace".

• Marked as answer by Friday, October 5, 2012 7:30 PM
Friday, September 28, 2012 9:22 PM

### All replies

• If i am not wrong you are looking for maximum no of combination. You Just have to make all the combination upto that position . you can write some small recursive function to achieve this if you are looking for something else let me know.

thanks

Rupesh Shukla

Friday, September 28, 2012 7:13 PM
• I want to calculate maximum numner of moves i can make in any 2-D array using above given condition. In visual c++ above code is working as i expected but its not working with Dev-C++ compiler and on ideone.com site compiler. I just want to know the reason where am i doing wrong?
Friday, September 28, 2012 7:23 PM
• I want to calculate maximum numner of moves i can make in any 2-D array using above given condition. In visual c++ above code is working as i expected but its not working with Dev-C++ compiler and on ideone.com site compiler. I just want to know the reason where am i doing wrong?

When you say it is not working what you mean by that.

Thanks

Rupesh Shukla

Friday, September 28, 2012 7:46 PM
• for Dev-C++ compiler is showing 0 as output for

2 1 1

2 1 1

whereas ideone.com compiler shows 1002 whereas answer should be 3 which is showing in visual c++ compiler only.

for

6 2 5 2

4 5 3 8

9 7 8 9

9 9 9 5

output should be 5 which is showing in visual c++ compiler but ideone.com is showing

2003.

One thing to be noticed in ideone.com compiler for both cases output is
1002(sum of digits is 3 which is actual answer)

2003(sum of digits is 5 which is actual answer)

I dont know how is that output coming in ideone.com

• Edited by Friday, September 28, 2012 8:05 PM
Friday, September 28, 2012 8:00 PM
• `Problem is it shows correct output in Visual C++(3 and 5) but shows 0 as output in Dev-C++ and 1002 2003 as output for same input when compiled on ideone.com online compiler. I am not able to find why is this so?Hope you can help me. `

I don't know if it matters but you do not assign a[r][c] a value so it will remain 0 as implicitly initialized.

Do all three systems have the same size int?  I suggest using INT_MAX and INT_MIN for your boundary conditions (instead of 99...).

Do the other compilers have debuggers?  If so, you should be able to step through the code on each one and see where the difference occurs.  If not, add some debugging calls to printf at the top of each for loop as a "trace".

• Marked as answer by Friday, October 5, 2012 7:30 PM
Friday, September 28, 2012 9:22 PM