DESRUG - Desrugenstein

The city of Desrugenstein is a complete mess. Looking at the map, it seems organized, since it was created in a square grid form, but there is no directions standard. Each corner says the directions you can go from there (north, south, west, east). The mayor Daniel Snake is headstrong and lazy enough to let everything as it is and forbid any change attempt. Unable to do much, the Master Spiritual Counsellor of Desrugenstein, Giordano Marfyn, asked you, Spiritual Counsellor Level XVII of Desrugenstein, lead programmer of Desrugenstein, to write a program to calculate the cost of going from a corner (x, y) to another corner (z, w), considering the messy streets.

Input

Input file contains several test cases. First line of each test case contains an integer N (1 ≤ N ≤ 10) that represents height and width of the grid that maps the city (a N x N grid). The input file ends with N = 0, and it should not be processed. Each one of the next N lines represents a street of the city, starting from the further north (N – 1) until the further south. In each one of these lines there are 4*N integers, 4 for each corner: A (north) B (south) C (west) D (east). Each one is 0 if it is not possible to go on the respective direction, or 1 if it is possible. After the city map, your program should read an integer P (1 ≤ P ≤ 100). Next P lines contain 4 integers each, x0 y0 x1 y1 representing the question: “What is the minimum cost to go from corner (x0 , y0) to corner (x1 , y1)?”. The cost to go from a corner to the nearest corner in any direction is 1.

Output

For each question, answer “Impossible” if there is no valid (respecting corners directions) path between the corners, or the minimum cost, if there is (are) path(s). Print a blank line after each test case.

Example

Input:
4
0 1 0 1 0 0 1 0 0 0 0 1 0 1 0 0
0 0 0 0 1 0 0 1 0 0 0 1 0 1 0 0
1 0 0 0 1 0 1 0 1 1 0 0 0 1 1 0
0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0
5
1 3 0 3
2 3 3 0
2 3 0 0
3 1 3 2
0 3 0 0
0

Output:
1
4
7
3
Impossible

Added by:Paulo Costa
Date:2012-02-09
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:UFU

hide comments
2020-02-11 02:11:12
Directions always point to cells within the grid. Don't print any blank lines, just each answer on its own line.
2012-08-25 07:20:14 vishal chaudhary
Got AC in first attempt...:)
2012-08-15 13:50:07 ♘Prabhat
@:D NSEW is <-> UP,DOWN,RIGHT,LEFT
i got WA by urs direction
2012-08-04 18:28:24 Archit Mittal
phew finally ac:)
2012-05-26 18:54:13 :D
1. NSEW <-> up,down,left,right
2. x-axis - left to right
y-axis - bottom to top (first line in the input has y coordinate of N-1)
3. I think my program assumed they are, but you will be better off if you just block directions on borders.

I agree, the description could have been better.
2012-05-26 11:03:35 Divanshu
Problem description is too unclear !
1. North is taken as upward direction ?
2. X-axis and y-axis start from the top or bottom in the grid ?
3. Are the directions assured to keep us within the map?

Last edit: 2012-05-26 11:36:57
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.