ALCATRAZ3 - THE HONEYCOMB MAZE

You won the lottery tickets to visit the famous Disneyland Hong Kong 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 empty 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

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. So, it is possible. Also, no blocks were repeated.


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

hide comments
2022-01-23 20:26:12 Amitayush Thakur
It is easy, but getting a 0.00 AC is hard. I tried multiple approaches but could, at best, get 0.02 only. I tried int8_t for minimal space, reduced the number of comparisons, made all functions inline, but nothing seemed to speed it up. Maybe changing recursion to stack-based implementation might help.

[NG]: Recursion should always be a distant second choice whenever an alternative makes sense; that being said, after Apr'2021 compiler updates, now even C has a significant lag per testfile. This means unfortunately for some problems, especially those with many testfiles, 0.00s or beating best time might not be possible anymore.

Last edit: 2022-01-23 23:06:39
2021-01-11 14:52:17
i have seen episode, iyer couldn't go in hong kong
2020-09-24 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.
2020-09-16 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.
2020-08-22 05:59:51
what about 1,1 in explanation
2020-08-19 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.
2020-06-22 19:51:52
The problem has an exponential time solution. Hint: Try to use backtracking and find the required path (similar to exhaustive search!)
2020-06-20 21:25:45
Phew, AC in 3rd Go. I forgot the maze was one indexed!

Last edit: 2020-06-20 22:15:18
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
2019-09-14 10:55:30
can anyone give me the solution, it looks like a dfs is too expensive, isn't it?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.