ALCATRAZ3  THE HONEYCOMB MAZE
You won the lottery tickets to visit the famous Disneyland HongKong with the Taarak Mehta ka Ulta Chasma family and Subramaniam Iyer gets stuck in the Honey Comb maze. He has a Phone along with him and no one else to help him out. He calls you and asks for help. Chuck the story getting into the problem now , There are N x M blocks of Honey combs in the maze and you are given a starting point. your task is to help Mr. Iyer find out whether or not he can traverse the maze and return to his original position. The constraint being that a honey comb ( Block ) once visited cannot be visited again . Also , he has to make a minimum of 'k' number of moves before returning to the starting point . The '.' represent the emty blocks whereas the '*' represent the blocks that can't be visited . from a block (x,y) Iyer can move only to blocks (x1,y) , (x+1,y) , (x,y+1) , (x,y1) . Help Mr. Iyer return to his original position.
Input
The first line of the input contains the dimensions of the maze ( N x M).
Second line of the input contains 'k' as described above .
The third line denotes the coordinates of the starting point ( 1n ) , ( 1m ) .
The next N lines contain the description of the Nth row .
Output
Output "YES" if it's possible .
Else output "NO" .
Constraints:
1<=N,M<=100
Example
Input: 5 5
14
1 2
. . . * *
* . . . *
* . . . .
. * . . .
. * . . *
Output: YES
Explanation of the test case :
1,2  2,2  3,2  3,3  4,3  5,3  5,4  4,4  4,5  3,5  3,4  2,4  2,3  1,3  1,2
14 moves were made ( No. of dashes (  )) .
So , its possible . Also , no blocks were repeated .
hide comments
odavidson707:
20180116 21:38:27
I checked spoj toolkit and found that a 'k' of 1 must always yield yes. This is wrong, it is impossible to have a cycle of length 1. 

thakur13:
20171014 18:24:05
Input contains spaces.


namitp:
20170913 15:29:11
Easy One....


namitp:
20170913 15:29:11
Easy One....


d_skyhawk:
20170829 12:50:58
Just dfs 

deepak_d14:
20170824 09:21:09
AC in first go!!!! Use dfs and flood fill algorithm. Last edit: 20170824 09:21:24 

namtran4194:
20170723 08:47:08
see the testcases in http://spojtoolkit.com/, some testcases are special, i got AC after that 

sas1905:
20170620 06:25:21
@Sushovan Sen Input is space separated got many WA's because of that and @Rohit Agarwal for k=0 ans will be yes always..!! Last edit: 20170626 01:37:24 

pranav0123:
20170531 09:44:46
Is there any polynomial time algorithm to solve this problem. I applied an exponential algorithm using dfs and backtracking and it got accepted. 

Rohit Agarwal:
20170503 15:05:20
For K = 0 , and starting point being '.' then, the output should be YES. In the spoj toolkit the answer is mentioned as NO. What should be the correct output? Last edit: 20170503 15:05:51 
Added by:  Alcatraz 
Date:  20170129 
Time limit:  0.100s1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU 
Resource:  Own Problem 