YUVRAJ - Editorial
PROBLEM NAME : YUVRAJ
CONTEST CODE : ALPH2016
DIFFICULTY:
EASY.
PREREQUISITES:
DP.
PROBLEM:
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.
QUICK EXPLANATION:
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.
EXPLANATION:
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.