Description
【题意】
广阔的大海地图可以由矩形阵列表示。
矩阵的元素由数字0和1组成。0表示海水。数字1代表军舰。
同一舰队的定义为沿军舰数字上下左右还是军舰数字1则为同一舰队。
求给定矩形阵列的舰队个数。如:矩阵
0111100011
1011110100
1011100111
0000000011
有4个舰队。
其中有艘军舰发生故障,负责救援的人员从固定的救援军舰赶往故障处。处于安全考虑,救援人员只能通过舰队内部到达故障点。
【输入格式】
第一行两个整数n,m (1 < = n,m< = 1000)
下来是n×m矩阵
下来一行K(1 < = K < =2000) ,代表下来K行有K个询问。每行为X1,Y1,X2,Y2代表两艘军舰的海上坐标。
【输出格式】
如果两艘军舰属于同一舰队那么输出它们之间最短的内部距离,若两艘军舰不属于同一舰队,那么请输出"Impossible".
注意: 舰队由军舰构成。^_^
【样例输入】
4 10
0111100011
1011110100
1011100111
0000000011
2
1 3 2 6
1 3 4 10
【样例输出】
4
Impossible
4 10
0111100011
1011110100
1011100111
0000000011
2
1 3 2 6
1 3 4 10