YES
唉。。一道DFS题目，也可以BFS解。这道题今天搞了一天，有些小悲催。。
刚开始不知道怎么想的，用递归总是超时，最后都出现了栈溢出的错误提示。。。
后来就一直WA。。。好崩溃的说。
最后决定用栈来解这道题目，但发现在判定是否走过的路的数组上出现了问题。
就是你走过的路可以置1，但是当你发现这条路走不通时，如何把走过的路置回0呢？
我没想出来，后来看到别人用队列做的，但他的判断数组设置成了3维的，
最后又加了一个来看 某一点4个方向是否都遍历到，遍历过的置1，这样就避免重复走同一条路的情况。
我最后还是决定用递归做了，恩。。AC后发现7000+MS，跟人家0MS 的比快哭了的说。。
后来，看了看别人的剪枝，放到自己代码上，结果骤减到62MS ( ⊙o⊙ )！！！！
搜索的精髓果然还是在剪枝上啊！！
这道题难点就在于如何判断转向上，我是设置的dis数组上右下左（0,1,2,3），可以发现 i对2取模，为0时判定是上下走，为1时判定左右走，这样根据之前的方向和现在的方向就可以知道是否转向了。
强大的剪枝就是：
当转向2次后，来判定当前的点和终点 是否在同一条线路，如果不在同一条线路就直接返回。
代码：
#include <stdio.h>
#include <string.h>
int map[1005][1005],vis[1005][1005];
int dis[4][2]={-1,0,0,1,1,0,0,-1};
int n,m,f_x,f_y;
bool ispos;
// dfs开始
void dfs(int x,int y,int direct,int turn)
{
// 如果转向大于2 或者 已经找到了 则直接返回
if(turn>2 || ispos==1) return;
// 如果到了目标，直接判定可以连接，因为之前转向大于2的都返回了
if(x==f_x && y==f_y)
{
ispos=true;
return;
}
// 强大的剪枝啊=。=
if(turn==2)
{
if(x!=f_x && y!=f_y) return;
else if(x==f_x)
if(direct!=1) return;
else if(y==f_y)
if(direct!=0) return;
}
int i,xx,yy;
// 四个方向的遍历
for(i=0;i<4;++i)
{
xx=x+dis[i][0];
yy=y+dis[i][1];
// 边界判定
if(xx<1 || yy<1 || xx>n || yy>m || vis[xx][yy]==1) continue;
// 如果下一个点是0或者终点
if(map[xx][yy]==0 || (xx==f_x && yy==f_y))
{
vis[xx][yy]=1;
//根据原来的方向来确定是否转向
if(direct==-1) dfs(xx,yy,i%2,turn);
else if(direct==0)
{
if(i%2==1) dfs(xx,yy,1,turn+1);
else dfs(xx,yy,0,turn);
}
else if(direct==1)
{
if(i%2==0) dfs(xx,yy,0,turn+1);
else dfs(xx,yy,1,turn);
}
vis[xx][yy]=0;
}
}
}
int main()
{
int i,j,q,s_x,s_y;
while(scanf("%d%d",&n,&m)!=EOF)
{
if(n==0 && m==0) break;
// 输入
for(i=1;i<=n;++i)
for(j=1;j<=m;++j)
scanf("%d",&map[i][j]);
scanf("%d",&q);
while(q--)
{
scanf("%d%d%d%d",&s_x,&s_y,&f_x,&f_y);
// 如果搜寻的两个点不相等或者搜寻的点是空点(即搜寻的点有0)
if(map[s_x][s_y]!=map[f_x][f_y] || map[s_x][s_y]==0 )
{
printf("NO\n");
continue;
}
// 如果搜寻两个点都为本身（去掉后增加了点时间）
if(s_x==f_x && s_y == f_y && map[s_x][s_y]!=0)
{
printf("NO\n");
continue;
}
// 初始化
memset(vis,0,sizeof(vis));
ispos=false;
dfs(s_x,s_y,-1,0);
// 判断输出
if(ispos) printf("YES\n");
else printf("NO\n");
}
}
return 0;
}还有WA的可能就是因为方向的问题。。。
提供一组别人想的测试数据：
ACM-搜索之连连看——hdu1175,布布扣,bubuko.com
原文：http://blog.csdn.net/lttree/article/details/22101493