Problem1049--宽搜4(海上舰队Ⅱ——救援任务)

1049: 宽搜4(海上舰队Ⅱ——救援任务)

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 6  Solved: 5
[Status] [Submit] [Creator:]

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

Sample Input Copy

4 10 
0111100011 
1011110100 
1011100111 
0000000011 
2 
1 3 2 6 
1 3 4 10 

Sample Output Copy

4 
Impossible

Source/Category