Answered by:
Maximum Path length
Question

This Program finds the maximum path from any position in a 2D 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 1
has 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[0][c], a[1][c], a[2][c]....a[r1][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][0], a[r][1], a[r][2]....a[r][c1] 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[0]; 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 DevC++ 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
Answers

Problem is it shows correct output in Visual C++(3 and 5) but shows 0 as output in DevC++ 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 wincod 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 2D array using above given condition. In visual c++ above code is working as i expected but its not working with DevC++ 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 2D array using above given condition. In visual c++ above code is working as i expected but its not working with DevC++ 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 DevC++ 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 wincod 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 DevC++ 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 wincod Friday, October 5, 2012 7:30 PM
Friday, September 28, 2012 9:22 PM