麻将游戏

题目链接： http://bailian.openjudge.cn/practice/2802/

Description

　　在一种”麻将”游戏中，游戏是在一个有W＊H格子的矩形平板上进行的。每个格子可以放置一个麻将牌，也可以不放（如图所示）。玩家的目标是将平板上的所有可通过一条路径相连的两张相同的麻将牌，从平板上移去。最后如果能将所有牌移出平板，则算过关。 
　　这个游戏中的一个关键问题是：两张牌之间是否可以被一条路径所连接，该路径满足以下两个特性： 
　　1. 它由若干条线段组成，每条线段要么是水平方向，要么是垂直方向。 
　　2. 这条路径不能横穿任何一个麻将牌 (但允许路径暂时离开平板)。 
　　这是一个例子： 

       在（1，3）的牌和在(4, 4)的牌可以被连接。(2, 3)和(3, 4)不能被连接。 
　　你的任务是编一个程序，检测两张牌是否能被一条符合以上规定的路径所连接。

Input

　　输入文件的第一行有两个整数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，则表示输入结束。

Output

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

Sample Input

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

Sample Output

4

3

0

算法分析：

这道题可以参考上一篇文章：最少转弯数

最少转弯数这一道题计算出发点到目的点的最少转弯数，本题计算两个点之间的路径的线段的段数。这个段数其实就是转弯数加1.所以可以按照上一篇文章的做法求解。这一题当中，麻将牌可以离开平板，所以在表示平板的0/1矩阵地图周围构造一个环形通路，也就是外面有一圈0，以便广搜时可以走这一条路。

大体的思路就是在广搜时，对每一个可以前进的方向都一直前进直到不可行走为止，然后再从下一个方向继续广搜。具体描述见最少转弯数这篇文章的分析和代码注释。

PS：本题部分资料整理自下面两篇文章。

http://blog.csdn.net/SSL_ZZY/article/details/53856843

http://www.cnblogs.com/A1269180380/p/6340704.html

下面的代码是由最少转弯数的代码修改而来：

#include<cstdio>  
#include<cstring>  
#include<queue>  
using namespace std;

const int dx[]={0,1,0,-1};//右下左上
const int dy[]={1,0,-1,0};
struct point
{
    int x,y,turn;
}_begin,_end,p;

queue<point> q;
int n,m,_map[101][101];
bool used[101][101];  

int fun();//统计从 _begin到达 _end的最少拐弯数。拐弯数加1就是线段数。 

int main()
{
    freopen("MAHJONG_data/MAHJONG7.in","r",stdin);
    freopen("MAHJONG_data/MAHJONG7.ans","w",stdout);
    int w,h,i,j,x1,y1,x2,y2;
    char ch;
    scanf("%d%d",&w,&h);getchar();//吸收行末尾回车符
    n=h;m=w; // n行，m列 
    
    //下面构造地图，把原来的字符矩阵转换为0/1矩阵表示的地图 
    //构造地图周围的环形通路 
    for(i=0;i<=n+1;i++) {  _map[i][0]=0;  _map[i][m+1]=0; }
    for(j=0;j<=m+1;j++) {  _map[0][j]=0;  _map[n+1][j]=0; }
    //for(j=0;j<=m+2;j++) _map[n+2][j]=1;  构造矩阵底部围墙 
    //for(i=0;i<=n+2;i++) _map[i][m+2]=1;  构造矩阵右侧围墙 
    for(i=1;i<=n;i++)//输入地图，把地图转换为0/1矩阵 
    {
        for(j=1;j<=m;j++)
        {
            ch=getchar();
            if(ch==' ') _map[i][j]=0; //0表示可以行走 
            else _map[i][j]=1;        //1表示不可以行走 
        }
        getchar();//吸收行末尾回车符
    }
    n++; m++;//因为环形通路的存在，行和列数目都增加 1。
    
    /*for(i=0;i<=n;i++)
    {
        for(j=0;j<=m;j++) printf("%d",_map[i][j]);
        printf("
");
    }
    printf("
-----------
");*/
    
    while(scanf("%d%d%d%d",&x1,&y1,&x2,&y2)!=EOF)
    {
        if(x1==0&&x2==0&&y1==0&&y2==0) break;
        else
        {
            _begin.x=y1;
            _begin.y=x1;
            _end.x=y2;
            _end.y=x2;
            
            _map[y2][x2]=0;//要使得目的地可以到达 
            fun();
            _map[y2][x2]=1;//还原地图 
        }
    }
    
    return 0;
}
int fun()
{
    memset(used,0,sizeof(used));
    while(!q.empty()) q.pop();//清空队列
     
    q.push(_begin);
    q.front().turn=0;  
    while(!q.empty())
    {
        for(int i=0;i<4;i++)
        {
            p.x=q.front().x+dx[i];  
            p.y=q.front().y+dy[i];
            //从队头出发往dx[i]和dy[i]方向一直走，直到遇到边界或高山则停止，再从原队头换下一个方向走 
            while(p.x>=0&&p.x<=n&&p.y>=0&&p.y<=m&&!_map[p.x][p.y]) //环形通路也是可以行走的 
            {
                if(!used[p.x][p.y])
                {
                    if(p.x==_end.x&&p.y==_end.y)
                    {
                        printf("%d
",q.front().turn+1);//注意输出的是当前队头的转弯次数。 
                        return 0;  
                    }  
                    used[p.x][p.y]=1;  
                    p.turn=q.front().turn+1;  
                    q.push(p);  
                }
                p.x+=dx[i];
                p.y+=dy[i];
            }  
        }  
        q.pop();//当前队头元素已经不能再扩展，可以删除队头 
    }
    printf("0
");//假如广搜无法到达目的地，那么输出0 
}