Question link: https://www.codechef.com/COOK92B/problems/CO92MATR
The problem asked that, we have replace each -1 with +ve integers, such that all rows and columns are in non-decreasing order. So, i am taking a 2D array and taking the input. But, to go to each '-1' and comparing it with its neighbouring elements(which can be atmax 4), will require use of LOTS OF NESTED LOOPS. And adding to that we have to consider all the possible cases where -1 can be,like at the top or top-left or middle of the matrix.
Is there is any easier and compact approach to this problem ?
Asked by: Samrat_De on April 7, 2019, 6:34 p.m. Last updated on April 7, 2019, 6:34 p.m.
Think about this approach:
Traverse the matrix in row wise manner...
Now ,when traversing the elements keep a check ,if the element just below and towards the right are in the sense that the increasing order is maintained other wise the arrangement is not possible...
consider this example...
1 2 2 3 1 -1 7 -1 6 -1 -1 -1 -1 -1 -1 -1
Now in 1 st row traversal ,you traverse 1 ,2,2, 3..in each case you compare it with the bottom and right member ...the sequence is maintained.
Similarly do it with the 2nd row and all the rows;
if at any time ,you visit a -1.. compare the values of the element just above -1 and just towards the left of it....whatever be the greater of them ..store it in the index containing -1(because that is the least value you can store in it..if the sequene is to be maintained....
and then again perform a check of the sequence ... i.e comparing it with the right and bottom element.... do the same and avoid check for the corner elements...
Hope this would be helpful.. :)