127. 【宽度优先搜索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 <cstdio>
#include <iostream>
using namespace std;
char a[77][77];
int h, t, q[6407][4];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int w1, h1, a1, a2, b1, b2;
void bfs (int, int, int, int);
int main()
{
	scanf ("%d%d", &w1, &h1);
	// 两个函数清除缓冲区 
	cin.clear();
	cin.sync();
	for (int i = 1; i <= h1; i++)
	{
		cin.getline (a[i], w1);
		// 同上 
		cin.clear();
		cin.sync();
	}
	for (int i = 0; i <= h1 + 1; i++)
	{
		for (int j = 0; j <= w1 + 1; j++)
		{
			if (i == 0 || i == h1 + 1 || j == 0 || j == w1 + 1)
				a[i][j] = ' ';
		}
	}
	while (1)
	{
		scanf ("%d%d%d%d", &a1, &a2, &b1, &b2);
		if (a1 == 0 && a2 == 0 && b1 == 0 && b2 == 0)
			break;
		bfs (a1, a2, b1, b2);
	}
	return 0;
}
void bfs (int a1, int a2, int b1, int b2)
{
	h = 0, t = 1;
	a[a2][a1] = 'X';
	q[t][0] = a2, q[t][1] = a1, q[t][2] = 0, q[t][3] = 0;
	while (h < t)
	{
		h++;
		int x = q[h][0];
		int y = q[h][1];
		for (int i = 0; i < 4; i++)
		{
			int xx = x + dx[i];
			int yy = y + dy[i];
			if (xx >= 0 && xx <= w1 + 1 && yy >= 0 && yy <= h1 + 1 && a[xx][yy] == ' ')
			{
				t++;
				a[xx][yy] = 'X';
				q[t][0] = xx;
				q[t][1] = yy;
				q[t][2] = i;
				q[t][3] = q[h][3];
				if (q[t][2] != a[h][2])
					q[t][3]++;
				if (xx == b1 && yy == b2)
				{
					printf ("%d\n", q[t][3] + 1);
					return;
				}
			}
		}
	}
}