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 (x-1,y)  ,  (x+1,y)  ,  (x,y+1)  ,  (x,y-1) . 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 ( 1-n ) , ( 1-m ) .

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
sajalagrawal14: 2020-01-04 16:33:26

remember
1)it is longest path algorithm in which no polynomial time complexicity algorithm is known . only exponential will work.
2)in certain cases of of longest path algorithm like trees , polynomial tc is known

sofianelew_97: 2019-09-14 10:55:30

can anyone give me the solution, it looks like a dfs is too expensive, isn't it?

Harish Reddy Kolanu: 2019-01-23 14:56:19

Ac using DFS. Easy one

maya_nk99: 2019-01-11 08:51:34

Getting WA in 4th test case can anyone plz help???

be1035016: 2018-06-21 06:10:29

easy one AC in one go!!!

weathervane: 2018-06-02 19:54:39

The question says constraints: 1<=N,M<=100. It can't be – I don't believe it is possible to solve the "longest path problem" for 10,000 nodes in such a short time. I wasted a huge amount of time trying to get this working for the conditions stated before submitting a brutal dfs. Can you please edit the question to show the true constraints and not mislead us?

Last edit: 2018-06-02 19:58:55
saihemanth9019: 2018-05-16 15:33:35

Exponential answer works. According to Spoj Toolkit, n<=5.

odavidson707: 2018-01-16 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: 2017-10-14 18:24:05

Input contains spaces.
AC using Dijkstra 0.0 sec

namitp: 2017-09-13 15:29:11

Easy One....
Ac in 2nd Go Spaces in input costed me 1 WA..


Added by:Alcatraz
Date:2017-01-29
Time limit:0.100s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU
Resource:Own Problem