连连看
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;
}
