If current direction is row , then count paths for two cases 1 ) We reach here through previous row . 2 ) We reach here through previous column , so number of turns k reduce by 1.
if ( d == 0 ) return dp [ i ] [ j ] [ k ] [ d ] = countPathsUtil ( i , j - 1 , k , d ) + countPathsUtil ( i - 1 , j , k - 1 , ! d ) ;