当前位置:首页 > 搜索 > 广度优先搜索 > 正文
SSOJ2317麻将游戏
3423+

题目大意:麻将放在整齐的格子中,只要两个麻将能用若干条直线连起来,不穿过其他麻将就能拿走,请问至少需要多少条直线?(连连看)

题目描述

在一种“麻将”游戏中,游戏是在一个有w*h格子的矩形平板上进行的。每个格子可以放置一个麻将牌,也可以不放(如图所示)。玩家的目标是将平板上的所有可通过一条路径相连的两张相同的麻将牌,从平板上移去。最后如果能将所有牌移除平板,则算过关。

这个游戏中的一个关键问题是:两张牌之间是否可以被一条路径所链接,该路径满足以下两个特性:

(1)它由若干条线段组成,每条线段要么是水平方向,要么是垂直方向。

(2)这条路径不能横穿任何一个麻将牌(但允许路径暂时离开平板)

这是一个例子:

在(1,3)的牌和在(4,4)的牌可以被连接。(2,3)和(3,4)不能被连接。

你的任务是编一个程序,检测两张牌是否能被一条符合以上规定的路径所连接。

 

输入

第一行有两个整数w,h(1<=w,h<=75),表示平板的宽和高。接下来h行描述平板信息,每行包含w个字符,如果某个格子有一张牌,则这个格子上有个’X’,否则是一个空格。平板上最左上角格子的坐标为(1,1),最右下角格子的坐标为(w,h)。接下来的若干行,每行有四个数x1,y1,x2,y2,且满足1<=x1,x2<=w,1<=y1,y2<=h,表示两张牌的坐标(这两张牌的坐标总是不同的)。如果出现连续四个0,则表示输入结束。

输出

对于每一对牌输出占一行,为连接这一对牌的路径最少包含的线段数。如果不存在路径则输出0.

样例输入

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
3
0

解题思路

本题跟上一题“最少转弯问题”是一样的,需要转多少次弯,就需要多少条直线(+1)。与上题不同的是,麻将外围可以走;思考一下,外围的话,只需要走外围那一圈,走到再外一圈就没多大意义了,因为外围一圈都是可以通过转弯到达的。因此,我们只需要将地图外围一圈围上空格让其可以走,同时让地图范围变为0到n+1、0到m+1,即可转成最少转弯问题。为了不判断边界,代码实现将地图所有边界+1,所有坐标+1了,即在再外围一圈围上障碍“X”。对于每组询问,步数数组都需要赋初值,并且把终点设为可以走,这样才能把步数填到终点的位置,在输出终点步数(直线数量)时,要把这个终点的障碍填回去,以免影响下一组询问。

注意:本题读入不好用scanf(“%s”, mp[i]),因为格式化输入输出,除了读字符以外,遇到空格回车都会暂停的,读不到空格或回车。因此,本地还是逐个字符来读比较合适,行末回车不要的话,可以读入不保存,即scanf(“%*c”)。

程序实现

About

坚决不Copy代码!

本文标签:,,,,,,,,

SSOJ2317麻将游戏:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!