Problem Description
“连
连看”相信很多人都玩过。没玩过也没关系，下面我给大家介绍一下游戏规则：在一个棋盘中，放了很多的棋子。如果某两个相同的棋子，可以通过一条线连起来
（这条线不能经过其它棋子），而且线的转折次数不超过两次，那么这两个棋子就可以在棋盘上消去。不好意思，由于我以前没有玩过连连看，咨询了同学的意见，
连线不能从外面绕过去的，但事实上这是错的。现在已经酿成大祸，就只能将错就错了，连线不能从外围绕过。
玩家鼠标先后点击两块棋子，试图将他们消去，然后游戏的后台判断这两个方格能不能消去。现在你的任务就是写这个后台程序。
玩家鼠标先后点击两块棋子，试图将他们消去，然后游戏的后台判断这两个方格能不能消去。现在你的任务就是写这个后台程序。
Input
输
入数据有多组。每组数据的第一行有两个正整数n,m(0<n<=1000,0<m<1000)，分别表示棋盘的行数与列数。在接
下来的n行中，每行有m个非负整数描述棋盘的方格分布。0表示这个位置没有棋子，正整数表示棋子的类型。接下来的一行是一个正整数
q(0<q<50)，表示下面有q次询问。在接下来的q行里，每行有四个正整数x1,y1,x2,y2,表示询问第x1行y1列的棋子与第
x2行y2列的棋子能不能消去。n=0,m=0时，输入结束。
注意：询问之间无先后关系，都是针对当前状态的！
注意：询问之间无先后关系，都是针对当前状态的！
Output
每一组输入数据对应一行输出。如果能消去则输出"YES",不能则输出"NO"。
Sample Input
3 4 1 2 3 4 0 0 0 0 4 3
2 1 4 1 1 3 4 1 1 2 4 1 1 3 3 2 1 2 4 3 4 0 1 4 3 0 2 4 1 0 0 0 0 2 1 1 2 4 1 3
2 3 0 0
Sample Output
YES NO NO NO NO
YES
一开始自己写了一个，通过用递归来弄的，但是堆溢出了，唉。。
（一）
#include<iostream>
using namespace std;
int a[1000][1000];
int m,n;
int p,q,b,c;
int visited[1000][1000][4];
int z=0;//转折次数
bool S(int i,int j,int l)//走到i ， j 点处，上一步走的方向是l
{
bool x=false;
for(int h=0;h<4;h++)
{
if(visited[i][j][h])
{
visited[i][j][h]=0;
if((l+h)%2!=0) z++;
if(z==3) return false;
switch (h)
{
case 0 : if(i-1==b && j==c) return true;
if((a[i-1][j])==0 && i-1>=0)
x=S(i-1,j,h); break; //0为上
case 1: if(i==b && j+1==c) return true;
if((a[i][j+1])==0 && j+1<n)
x=S(i,j+1,h); break; //1为右
case 2: if(i+1==b && j==c)
return true;
if((a[i+1][j])==0 && i+1<m)
x=S(i+1,j,h); break; //2为下
case 3: if(i==b && j-1==c) return true;
if((a[i][j-1])==0 && j-1>=0)
x=S(i,j-1,h); //3为左
}
if(x) return x;
if((l+h)%2!=0) z--;
}
}
return false;
}
void main()
{
int w;
bool x=false;
while(cin>>m>>n)
{
if(m==0 &&n==0) break;
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
{
cin>>a[i][j];
}
cin>>w;
for(i=0;i<w;i++)
{
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
for(int y=0;y<4;y++)
visited[i][j][y]=1;
cin>>p>>q>>b>>c;
p--; q--; b--; c--;
if(p==b && q==c && a[b][c]!=0)
{
cout<<"YES"<<endl;
continue;
}
if(a[p][q]!=a[b][c] || a[p][q]==0 || a[b][c]==0)
{
cout<<"NO"<<endl;
continue;
}
z=0;
for(int j=0;j<4;j++)
{
if(visited[p][q][j])
{
visited[p][q][j]=0;
switch (j)
{
case 0 : if(p-1==b && q==c) x=true;
if((a[p-1][q])==0 && p-1>=0)
x=S(p-1,q,j); break; //0为上
case 1: if(p==b && q+1==c) x=true;
if((a[p][q+1])==0 && q+1<n)
x=S(p,q+1,j); break; //1为右
case 2: if(p+1==b && q==c) x=true;
if((a[p+1][q])==0 && p+1<m)
x=S(p+1,q,j); break; //2为下
case 3: if(p==b && q-1==c) x=true;
if((a[p][q-1])==0 && q-1>=0)
x=S(p,q-1,j); //3为左
}
if(x) break;
}
}
if(x) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
}
}
using namespace std;
int a[1000][1000];
int m,n;
int p,q,b,c;
int visited[1000][1000][4];
int z=0;//转折次数
bool S(int i,int j,int l)//走到i ， j 点处，上一步走的方向是l
{
bool x=false;
for(int h=0;h<4;h++)
{
if(visited[i][j][h])
{
visited[i][j][h]=0;
if((l+h)%2!=0) z++;
if(z==3) return false;
switch (h)
{
case 0 : if(i-1==b && j==c) return true;
if((a[i-1][j])==0 && i-1>=0)
x=S(i-1,j,h); break; //0为上
case 1: if(i==b && j+1==c) return true;
if((a[i][j+1])==0 && j+1<n)
x=S(i,j+1,h); break; //1为右
case 2: if(i+1==b && j==c)
return true;
if((a[i+1][j])==0 && i+1<m)
x=S(i+1,j,h); break; //2为下
case 3: if(i==b && j-1==c) return true;
if((a[i][j-1])==0 && j-1>=0)
x=S(i,j-1,h); //3为左
}
if(x) return x;
if((l+h)%2!=0) z--;
}
}
return false;
}
void main()
{
int w;
bool x=false;
while(cin>>m>>n)
{
if(m==0 &&n==0) break;
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
{
cin>>a[i][j];
}
cin>>w;
for(i=0;i<w;i++)
{
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
for(int y=0;y<4;y++)
visited[i][j][y]=1;
cin>>p>>q>>b>>c;
p--; q--; b--; c--;
if(p==b && q==c && a[b][c]!=0)
{
cout<<"YES"<<endl;
continue;
}
if(a[p][q]!=a[b][c] || a[p][q]==0 || a[b][c]==0)
{
cout<<"NO"<<endl;
continue;
}
z=0;
for(int j=0;j<4;j++)
{
if(visited[p][q][j])
{
visited[p][q][j]=0;
switch (j)
{
case 0 : if(p-1==b && q==c) x=true;
if((a[p-1][q])==0 && p-1>=0)
x=S(p-1,q,j); break; //0为上
case 1: if(p==b && q+1==c) x=true;
if((a[p][q+1])==0 && q+1<n)
x=S(p,q+1,j); break; //1为右
case 2: if(p+1==b && q==c) x=true;
if((a[p+1][q])==0 && p+1<m)
x=S(p+1,q,j); break; //2为下
case 3: if(p==b && q-1==c) x=true;
if((a[p][q-1])==0 && q-1>=0)
x=S(p,q-1,j); //3为左
}
if(x) break;
}
}
if(x) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
}
}