有一种“麻将”游戏,是在一个有M×N格子的矩形平板上进行的。每个格子可以放置一个麻将牌,也可以不放(如图所示)玩家的目标是将平板上的所有可通过一条路径相连的两张相同的麻将牌,从平板上移去。最后如果能将所有牌移出平板,则算过关。
这个游戏中的一个关键问题是:两张牌之间是否可以被一条路径所连接,该路径满足以下两个特性:
1.它由若干条线段组成,每条线段要么是水平方向,要么是竖直方向。
2.这条路径不能横穿任何一个麻将牌,但允许路径暂时离开平板。
求一对牌之间最少包含的线段数,如果不存在路径则输出0。
第一行有两个整数M,N (1<=M,N<=75),表示平板的宽和高。接下来N行描述平板信息,每行包含M个字符,如果某格子有一张牌,则这个格子上有个‘X’,否则是一个空格。平板上最左上角格子的坐标为(1,1),最右下角格子的坐标为(M,N)。接下来的若干行,每行有四个数x1,y1,x2,y2,且满足1<=x1,x2<=M,1<=y1,y2<=N,表示两张牌的坐标,这两张牌的坐标总是不同的。如果出现连续四个0,则表示输入结束。
对于每一对牌输出占一行,为连接这一对牌的路径最少包含的线段数。如果不存在路径则输出0。
请输入正确的证书编号
学员姓名:孙兴民
课程:Scratch Level 1
发证日期:2019.08.15