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
harshiscoding:
20210111 14:52:17
i have seen episode, iyer couldn't go in hong kong 

sarkybastard:
20200924 23:55:32
The defining feature of a honeycomb is its hexagonal structure, so to call this problem honeycomb maze, and then define it as a square matrix is whatchamacallit... daft. 

arnav7060:
20200916 19:48:28
Got accepted in 13th try. If you are a beginner like me in these concepts. Don't worry even one complete question can take your full day but you would get to learn a lot. 

father3301:
20200822 05:59:51
what about 1,1 in explanation


sadman15019:
20200819 19:30:23
solved using direction array and basic dfs concept..keep in mind that the cycle can be "greater than" or "equal" to k. 

aditop:
20200622 19:51:52
The problem has an exponential time solution. Hint: Try to use backtracking and find the required path (similar to exhaustive search!) 

snorlax186:
20200620 21:25:45
Phew, AC in 3rd Go. I forgot the maze was one indexed! Last edit: 20200620 22:15:18 

sajalagrawal14:
20200104 16:33:26
remember


sofianelew_97:
20190914 10:55:30
can anyone give me the solution, it looks like a dfs is too expensive, isn't it?


Harish Reddy Kolanu:
20190123 14:56:19
Ac using DFS. Easy one 
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 