1127. 【宽度优先搜索BFS】麻将游戏

题目描述

在一种"麻将"游戏中，游戏是在一个有W＊H格子的矩形平板上进行的。

每个格子可以放置一个麻将牌，也可以不放（如图所示）。玩家的目标是将平板上的所有可通过一条路径相连的

两张相同的麻将牌，从平板上移去。最后如果能将所有牌移出平板，则算过关。

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

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

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

这是一个例子：

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

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

输入

从文件 majiang.in 中读入数据。

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

输出

输出到文件 majiang.out 中。

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

样例输入

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

样例输出

4
4
0

本蒟蒻damn马

为各位神犇奉上！

#include<bits/stdc++.h>
using namespace std;
int a1[101],a2[101],b1[101],b2[101],bz[102][102],d[10001][4],dx[4]={-1,0,0,1},dy[4]={0,-1,1,0};
char mp[102][102];
int main()
{
	int n,m;
	cin>>m>>n;
	for(int i=1;i<=n;i++)
	{
		string s;
		getline(cin,s);
		for(int j=1;j<=m;j++)
		{
			mp[i][j]=s[j-1];
		}
	}
	int a,b,c,d1,num=1;
	cin>>a>>b>>c>>d1;
	while(a!=0 and b!=0 and c!=0 and d1!=0)
	{
		a1[num]=a;
		a2[num]=b;
		b1[num]=c;
		b2[num]=d1;
		num++;
		cin>>a>>b>>c>>d1;
	}
	for(int i=1;i<=num;i++)
	{
		d[1][0]=a1[i];
		d[1][1]=a2[i];
		d[1][2]=-1;
		d[1][3]=0;
		memset(bz,0,sizeof(bz));
		int head=0,tail=1,turn=0;
		while(head<tail)
		{
			head++;
			bool flag=true;
			for(int j=0;j<=3;j++)
			{
				int xx=d[head][0]+dx[j];
				int yy=d[head][1]+dy[j];
				if(xx>=0 and xx<=n+1 and yy>=0 and yy<=m+1 and mp[xx][yy]==' ' and !bz[xx][yy])
				{
					tail++;
					bz[xx][yy]=1;
					d[tail][0]=xx;
					d[tail][1]=yy;
					d[tail][2]=i;
					d[tail][3]=d[head][3];
					if(d[tail][2]!=d[head][2] and d[head][2]!=-1)
					{
						d[tail][3]++;
					}
				}
				if(xx==b1[i] and yy==b2[i])
				{
					cout<<d[tail][3]<<endl;
				}
			}
		}
	}
	return 0;
} 

不忍直视（捂脸