YUVRAJ - Editorial
PROBLEM NAME : YUVRAJ
CONTEST CODE : ALPH2016
In a n*m matrix consisting of say 0 and 1 find the number of rows that can be crossed if we can travel down the matrix (straight or diagonal) only via 0.
Make a separate matrix of order n*m where (i,j) 0<i<n,0<j<m represents if the player can reach that particular position or not. Travel this matrix and find the maximum rows crossed.
First of all create a nm matrix arr out of the given inputs, mark all the players as 1 and free spaces as 0. We can cross the free spaces only. Create another matrix dp of order nm again consisting 0 and 1 where 0 represents that we can reach that particular position.
First row of dp is same as arr, from the second row onwards dp[i][j] will be zero if either of dp[i-1][j], dp[i-1][j] or dp[i-1][j+1] is zero as we can travel one step down the matrix (straight or diagonal). Create the complete array dp.
Now travel through the matrix dp and find in which row the last 0 exists. That’s the final answer.