1127. 【宽度优先搜索BFS】麻将游戏 (Input: majiang.in, Output: majiang.out) 时间限制: 1 s 空间限制: 256 MB 具体限制

题目描述 　　在一种"麻将"游戏中，游戏是在一个有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

#include<bits/stdc++.h>
using namespace std;
int dx[4]= {0,0,-1,1},dy[4]= {1,-1,0,0};
char a[1010][1010];
bool bz[1010][1001];
int q[100010][6];

int main() {
	int h,w;
	cin>>w>>h;
	cin.clear();
	cin.sync();
	for(int i=0;i<=h+1;i++)
	{
		for(int j=0;j<=w+1;j++)
			bz[i][j]=0;
	}
	for(int i=1; i<=h; i++) {	
		for(int j=1;j<=w;j++)
		{
			char ch;
			do
			{
				 ch=getchar();
			}
			while(ch=='\n');
			a[i][j]=ch;
			
		} 
		cin.clear();
		cin.sync();
	}
	
	while(1)
	{
		int ax,ay,bx,by;
		cin>>ax>>ay>>bx>>by;
		bool f=false;
		int tail,head;
		if(ax==0&&ay==0&&bx==0&&by==0)return 0;
		else {
			tail=1;
			head=0;
			q[1][1]=ax;
			q[1][2]=ay;
			q[1][3]=0;
			do {

				head++;
				for(int i=0; i<=3; i++)
				{

					int x=q[head][1]+dx[i],y=q[head][2]+dy[i];
					while(x>=0&&x<=h+1&&y>=1&&y<=w+1&&bz[x][y]==0) 
					{

						if(x==bx&&y==by) 
						{

							cout<<q[tail][3]<<endl;
							f=true;
							break;
						}
						tail++;
						bz[x][y]=1;
						q[tail][1]=x;
						q[tail][2]=y;
						q[tail][3]=q[head][3]+1;
						x+=dx[i];
						y+=dy[i];
					}
				}
				if(f)break;
			}while(head<tail);
		}
	}
}

求大佬帮忙！ 0分WA