文理学院程序设计在线练习


Crazy Arcade

Time Limit: 1 Second(s)    Memory Limit: 32 MB

Total Submission(s): 3   Accepted Submission(s): 1
Problem Description

Little K is interested in BnB mode of the game Crazy Arcade recently.
He found it important to preview the exploding time of bombs ,so he worked hard at it.
Now, he has another question:
How to move to the safe area faster?
It takes little K 1 second to move 1 step in four directions, known as up, down, left and right.
We can assume that when Little K arrives at a safe area, all bombs in the map explode, and new bombs are generated. And it does not take any time.
In another word, when little k find a safe place in this round, he can detonate all the bombs in this round and move to next round. And it does not take any time.
Little K has already known the position of bombs in next k rounds.
Can you help him to calculate the minimum times to pass through all the explosions safe and sound?

Input

First line of the input is the number of test cases T.
The first line of each test case contains two integers n and k, which is the map’s size and the rounds of explosions.
Second line also contains two integers x and y, which means the initial position of Little K is row x and column y.
Then it comes k matrixes, each contains n rows and n columns, representing the map of the game.
The matrix only consists of 0(s) and 1(s). The safe areas are represented by 0(s), and dangerous areas are represented by 1(s) .There is no empty cell in the matrix.
1 <= T <= 20
1 <= N, K <=50
1 <= x, y <= N
Notes that there is at least 1 safe area in each explosion and if n > 10, there are at least 70% of areas are dangerous.

Output

An integer represents the minimum times (seconds) to move.

Sample Input
3
3 3
3 1
000
111
101
111
000
111
111
101
111
3 3
1 1
011
111
111
011
111
111
011
111
111
3 3
2 2
011
111
111
110
111
101
111
111
011
Sample Output
2
0
6
Hint

Explanation for test 1:
Little K is originally at the lower-left corner. The Sequence of action is: right ( avoid the first explosion ) , and up (avoid the following two explosions ).

Source

2018市赛