locked
Maximum Path length RRS feed

  • 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 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[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][0], a[r][1], a[r][2]....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[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 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

Answers


  • 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 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 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 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 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 wincod Friday, October 5, 2012 7:30 PM
    Friday, September 28, 2012 9:22 PM