连连看
Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 34807 Accepted Submission(s): 8657
Problem Description
“连连看”相信很多人都玩过。没玩过也没关系，下面我给大家介绍一下游戏规则：在一个棋盘中，放了很多的棋子。如果某两个相同的棋子，可以通过一条线连起来（这条线不能经过其它棋子），而且线的转折次数不超过两次，那么这两个棋子就可以在棋盘上消去。不好意思，由于我以前没有玩过连连看，咨询了同学的意见，连线不能从外面绕过去的，但事实上这是错的。现在已经酿成大祸，就只能将错就错了，连线不能从外围绕过。
玩家鼠标先后点击两块棋子，试图将他们消去，然后游戏的后台判断这两个方格能不能消去。现在你的任务就是写这个后台程序。
Input
输入数据有多组。每组数据的第一行有两个正整数n,m(0
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
struct node
{
int a,b,num;
}as,t,h;
int w[1001][1001];//储存 连连看数据
int w1[1001][1001];//标记是否走过
int k,n,m,l;
int x,y,e,f;
int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
void dfs()
{
queue<node>q;
q.push(h);//判断连连看 一个数据入队
w1[x][y]=1;//标记
while(!q.empty())
{
as=q.front();
q.pop();
for(int i=0;i<4;i++)//向四个方向搜索
{
t.a=as.a+dir[i][0];
t.b=as.b+dir[i][1];
t.num=as.num;
while(w[t.a][t.b]==0&&t.a>=1&&t.a<=n&&t.b>=1&&t.b<=m&&t.num<3&&w1[t.a][t.b]==0)
{//在满足条件的情况下（w【t.a】【t.b】=0且不出境和没有搜索过）可以不计步数
w1[t.a][t.b]=1;//标记状态
t.num+=1;//计步 以便入队 向别的方向搜索
q.push(t);
t.num-=1;//你懂的 (⊙o⊙)
t.a+=dir[i][0];
t.b+=dir[i][1];
}
if(t.a==e&&t.b==f&&t.num<3)//到达另一个且步数小于等同于2
{
cout<<"YES"<<endl;
return ;
}
}
}
cout<<"NO"<<endl;
return ;
}
int main()
{
while(cin>>n>>m)
{
if(n==0&&m==0)
break;
memset(w,0,sizeof(w));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
cin>>w[i][j];
}
cin>>l;
while(l--)
{
cin>>x>>y>>e>>f;
memset(w1,0,sizeof(w1));
if(w[x][y]!=w[e][f])//俩个不相同 就没必要搜索了
cout<<"NO"<<endl;
else if(x==e&&y==f)//俩个是一个 就等没必要搜索了
cout<<"NO"<<endl;
else if(w[x][y]==0&&w[e][f]==0)//空白就更没必要了
cout<<"NO"<<endl;
else
{
h.a=x;
h.b=y;
h.num=0;
dfs();
}
}
}
return 0;
}