首页 > 代码库 > Hdu 1175 连连看（DFS）
Hdu 1175 连连看（DFS）
Problem地址:http://acm.hdu.edu.cn/showproblem.php?pid=1175
因为题目只问能不能搜到，没问最少要几个弯才能搜到，所以我采取了DFS。
因为与Hdu 1728相比，都要考虑转弯次数，所以在判断转弯的次数上，两者可以相互借鉴。
这一点应该不难想到，在搜索前就应判断两点的值是否相等，以及两点的值中是否有0。如果不相等或其中一值为0，则可以判断是"NO"。
时间虽是10000ms，但只是这样，还是超时。
后来又加了一个数组walk[][]，用于记录走到这一点的最小转弯数。当第二次走到这点时，如果第二次的转弯数小于或等于之前的转弯数，则更新数组；否则，不再继续往这个方向走。加上这个数组，再时间上就算初步优化了。
之后又在网上看了看其他人的题解，发现还可以加上这两点：
1.判断回头，即在某个点选择方向时，不往回走。
2.走在一点时，如果此时转弯数为2，那么就要考虑此时与终点是否在同一行或在同一列。如果不在同一列或同一行，则势必要再转一次弯，那就超过2次了。因此当转弯数为2时，两点在同一列或同一行时才能继续往这方向走。
这两点起到了很大的作用，可以大大优化运行时间。
#include <iostream>#include <cstring>#include <cstdio>using namespace std;const int MAXN = 1000 + 2;int map[MAXN][MAXN];int walk[MAXN][MAXN];int dir[4][2] = { 1,0, -1,0, 0,1, 0,-1 };int opposite[4] = { 1,0,3,2 }; // 与i方向相反的值为opposite[i]int n,m;bool flag; // 最终能否搜到的标志int x1,y1,x2,y2;void Dfs( const int x,const int y,const int from,const int step );void Quick_judge(){ // 初次快速判断能否走到 int i; int x,y; if( map[x1][y1]!=map[x2][y2] ){ flag = false; return ; } if( map[x1][y1]==0 || map[x2][y2]==0 ){ flag = false; return ; } for( i=0;i<4;i++ ){ x = x1 + dir[i][0]; y = y1 + dir[i][1]; if( x==x2 && y==y2 ){ //此时已在终点 flag = true; return ; } Dfs( x,y,i,0 ); //开始搜索 }}void Dfs( const int x,const int y,const int from,const int step ){ if( flag ) return ; if( x==x2 && y==y2 && step<=2 ) //到达终点 flag = true; if( map[x][y] ) //非0，无法继续走 return ; if( walk[x][y]==-1 || step<=walk[x][y] ) //与走到该点的最小转弯数比较 walk[x][y]=step; else return ; if( step==2 ) //如果步数为2，则判断是否在同一行或同一列 if( x!=x2 && y!=y2 ) return ; int i; int nextX,nextY; int nextStep; for( i=0;i<4;i++ ){ if( i==opposite[from] ) //避免往回走 continue; nextX = x+dir[i][0]; nextY = y+dir[i][1]; nextStep = step; if( i!=from ) //转弯 nextStep++; if( nextX>0 && nextX<=n && nextY>0 && nextY<=m && nextStep<=2 ) Dfs( nextX,nextY,i,nextStep ); } return ;}int main(){ int i,j; int C; while( scanf("%d%d",&n,&m)!=EOF && (n||m) ){ for( i=1;i<=n;i++ ) for( j=1;j<=m;j++ ) scanf("%d",&map[i][j]); scanf("%d",&C); while(C--){ flag = false; memset( walk,-1,sizeof(walk) ); //flag与walk[][]的初始化 scanf("%d%d%d%d",&x1,&y1,&x2,&y2); Quick_judge(); if( flag ) printf("YES\n"); else printf("NO\n"); } } return 0;}
Hdu 1175 连连看（DFS）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。