1301: 又见连连看

Memory Limit：128 MB Time Limit：1.000 S Judge Style：Text Compare Creator：
Submit：25 Solved：6

Description

女生中流行一种被称为“连连看”的游戏。现在仅对这个游戏中，两张相同花色的游戏牌之间的寻路问题展开讨论。在一个大小为h行w列（1≤w, h≤75）的矩形棋盘的每一个小方格中，可能放了一张游戏牌也有可能没放。两张相同的游戏牌能够连接起来当且仅当满足下列条件：

1．从一张游戏牌到另一张游戏牌的连线，由若干水平或垂直线段构成；

2．这些线段中任何一条都不能穿越其他游戏牌，但棋盘边界外的线段可以不在棋盘内。

你的任务是：对于给定的棋盘布局，以及指定的两张游戏牌，判断是否存在一条满足上述条件的线路将他们连接起来，并且若存在这样的线路，求出需要的线段数最少的线路。

例如，图中第2列第3行的牌，能够和第5列第3行的牌连接，第1列第3行的牌，能够和第4列第4行的牌连接，而第2列第3行的牌不能够和第3列第4行的牌连接。


不允许普通用户打印题目，请教师登录后使用。如有疑问请联系管理员!

Input

输入包含对几种不同游戏情境的描述。每个描述的第一行包含两个整数 w 和 h （1 ≤w,h ≤ 75），即棋盘的宽度和高度。接下来的 h 行描述了棋盘这一行的内容，每一行都包含 W 个字符：如果该位置有游戏牌，则为“X”，如果没有游戏牌，则为空格。每个描述后面都有若干行，包含四个整数 x1、y1、x2、y2，每个整数满足 1≤ x1,x2≤ w，1 ≤ y1,y2 ≤h。这些是两个游戏牌的坐标。（左上角有坐标为(1,1)）。棋盘的游戏牌的没描述将以包含“0 0 0 0”的行结束。当w=h=0是表示输入结束，你的程序可不必处理这一行。

Output

  对于每个游戏棋盘，输出行“Board #n：”，其中 n 是测试数据的编号。然后，为与棋盘描述关联的每对游戏棋子输出一行。这些行中的每一行都必须以“Pair m：”开头，其中 m 是该对的编号（每个板以 1 开始计数）。后面跟着“k segments.”，其中 k 是连接两个游戏牌的路径的最小段数，如果无法如上所述连接两个游戏牌，则为“不可能”。不同游戏棋盘对应的不同输出之间以一个空行隔开。

Sample Input Copy 

5 4
XXXXX
X   X
XXX X
 XXX 
2 3 5 3
1 3 4 4
2 3 3 4
0 0 0 0
4 4
XXXX
XXXX
XXXX
XXXX
1 1 2 1
2 2 3 2
1 1 3 1
3 4 4 3
2 1 2 4
1 1 2 2
0 0 0 0
0 0

Sample Output Copy 

Board #1:
Pair 1: 4 segments.
Pair 2: 3 segments.
Pair 3: impossible.

Board #2:
Pair 1: 1 segments.
Pair 2: 1 segments.
Pair 3: 3 segments.
Pair 4: 4 segments.
Pair 5: 5 segments.
Pair 6: impossible.

Source/Category