Hello,
I'm trying to solve this problem but I'm getting a WA
in test-case 4
. My logic is that we start from the starting point and do all "possible" moves i.e U,D,L,R
. For each possible move, we transit from state si to state sj and we decrement the count of K
, while marking si as visited. If we arrive in the starting point again with k <= 0,
then the answer is "YES"
else we backtrack to previous state and do the next possible move.
To optimize it, I used a variable to see if we have already found a route that satisfies the constraints or not. If the variable is set we just return and don't explore to new states from the current state.
I took care of some following corner cases:-
1> If K > N * M
, ans should be NO
2> if starting point is '*'
, ans should be NO
3> if K = 0
and starting point is '.'
ans should be YES
I don't know which other cases I might be missing. I'd be glad if someone can find some error in the logic or share any corner cases.
CODE: http://ideone.com/lEqWXH
Thanks.