# 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 n*m 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 n*m 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.