Go Back
Instructions please ! (400)
Description

Sashank and Neeraj have come to SIES GST for the first time for ByteCamp2019. They have made tiny devices that broadcast their locations(X,Y). While walking around campus they noticed that (N) devices have fell down from their bag. Sashank has a monitor that shows location of all the devices and both of them are facing north. Neeraj has to collect all the devices avoiding walls as soon as possible and return back to Sashank(Xp,Yp). Help Sashank to provide instructions to Neeraj via phone.

Instructions are:
Move forward to next place
Turn towards left standing on same place
Turn towards right standing on same place
Turn backward standing on same place

Input

The first line of input contain an integer T denoting the number of test cases.
First line of each test case contains N denoting number of devices.
Next line has space separated integers Xp and Yp .
It is followed by a line containing 2 space separated integers Xmax and Ymax denoting number of horizontal and vertical elements.
Next Y line contain matrix of 1s and 0s. Where 0 is for walls and 1 is for path.
Next N lines have space separated X and Y coordinate of the devices.

Output

For each test case print minimum number of instructions to cover all device in same order as input.
Print “lost” without quotes if collecting all devices is not possible.

Constraints

T < 101
0 < N < 6
X, Y < 21

Example
Copy Input

Input:
2
2
5 2
10 4
0111111000
1101011011
1101110010
0111111111
3 0
1 2
1
3 3
4 4
1011
1011
1011
1011
0 0

Output:
18
lost

Explanation

Test case1:



FFLFFFFLFFFLFFFFLF->18 instructions

Test case2:
No possible path.

Single Round Match #07
3 hour contest



Announcement
Register for Bytecamp 2019 here: https://bytecamp19.hackerearth.com/

Problem Tags
maze , matrix,

Supported by our Coding Partner