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
2017-02-08 22:46:55 testing java
still, exponential passes, but limits suggest polynomial solution. Either tests are poor and time limit is wrong [simple test 30x30 with dots and path of length at least 120 takes a lot of time] or there should be some information suggesting, that exponential solution may do just fine (like proper limits or some additional information about graph).

RE :- Considered . Thanks

Last edit: 2017-02-10 14:24:59
2017-02-04 07:47:32 Jacob Plachta
Actual bounds are N,M <= 5...
2017-02-04 04:25:53 testing java
is there any bound on k?
2017-02-02 17:12:38
AC at the 4th attempt...
2017-01-31 14:50:06 mehmetin
@alcatraz: Are you sure test files are correct?

Reply :- Sorry for the inconvenience , test cases were corrected . Thanks for pointing out :D

Last edit: 2017-02-02 16:09:17
2017-01-30 09:44:53 mehmetin
I used n, m <= 100. I don't get runtime error.
2017-01-30 09:37:35 Jacob Plachta
What are the bounds?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.