麻将游戏
时间限制：1000MS 内存限制：256000KB
题目描述
在一种"麻将"游戏中，游戏是在一个有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
分析
这题我们可以用广搜BFS来做
这题我们可以根据前面的**最小转弯问题（BFS）**来做
最小转弯问题（BFS）
再加上一些特殊的输入和边界就行了
AC代码
#include<iostream>
using namespace std;
int m,n,s,o,x1,y1,x2,y2,head,tail,a[80][80],st[1000005][4],b[80][80];
int dx[5]={
0,0,1,0,-1};//四个反向
int dy[5]={
0,1,0,-1,0};
string str;
void bfs()
{
tail=1;head=0;//初值
st[1][1]=x1;st[1][2]=y1;st[1][3]=0;//直接定义初始值，后面的值都来自这个值
a[x2][y2]=0;//把终点拆掉，不然到不了这个点
do
{
head++;
for(int i=1;i<=4;i++)//四个反向
{
int x=st[head][1]+dx[i],y=st[head][2]+dy[i];
while(x>=0&&x<=n+1&&y>=0&&y<=m+1&&a[x][y]!=1)//判断边界
{
if(a[x][y]!=s)//必须要和上面的判断分开，否则会撞到自己建的墙而走不了
{
tail++;
a[x][y]=s;
st[tail][1]=x;//更新
st[tail][2]=y;
st[tail][3]=st[head][3]+1;
if(x==x2&&y==y2)//判断
{
cout<<st[tail][3]<<endl;
o=1;//有答案，可以到终点
return;
}
}
x+=dx[i];//一定要在if外，while里面原因同上
y+=dy[i];
}
}
}while(head<tail);
}
int main()
{
cin>>m>>n;
getline(cin,str);//吸掉换行
for(int i=1;i<=n;i++)//字符串读入
{
getline(cin,str);//因为有空格
for(int j=0;j<=m-1;j++)
if(str[j]=='X')a[i][j+1]=1;
}
s=1;
while(cin>>x1&&cin>>y1&&cin>>x2&&cin>>y2)
{
swap(x1,y1);swap(x2,y2);//因为题目输入不同，所以要交换
if(x1==0&&x1==y1&&y1==x2&&x2==y2) break;
s++;//简便，建自己的墙，每次加1，每次自己建的墙的值都会变
o=0;
bfs();
a[x2][y2]=1;//前面拆掉了墙，要补回去
if(o==0)cout<<0<<endl;//判断到不到的了终点
}
}
京公网安备 11010502036488号