这道题困扰我的不是算法问题。而是细节问题。不优化一直搜到底 时间是690ms左右
没有优化的dfs
#include<stdio.h> #include<string.h> #include<stdlib.h> char map[10][10]; int flag[10][10]; int way[4][2]={ 0,1,0,-1,1,0,-1,0 }; typedef struct { int x,y; } point; point sta; int n,m; int t; int dfs( int s,int x,int y ) { int i,xx,yy; if( map[x][y]=='D' && s==t ) return true; /*c++，true c用1*/ if( map[x][y]=='D' && s!=t ) return false; if( s>=t ) return false; for( i=0;i<4;i++ ) { xx=x+way[i][0] , yy=y+way[i][1]; if( xx>=0 && xx<n && yy>=0 && yy<m && map[xx][yy]!='X' && !flag[xx][yy] ) { flag[xx][yy]=1; if( dfs(s+1,xx,yy) ) return true; flag[xx][yy]=0; } } return false; } int main() { int i,j; while(scanf("%d%d%d",&n,&m,&t)&&(n||m||t)) { memset( flag,0,sizeof(flag) ); for( i=0;i<n;i++ ) { scanf("%s",map[i]);//在这里是关键地方，我就是死在这里了，c里面先用getchar()消去回车。然后getchar()一个个接收。但是不幸的是wa了！！这里最好用 %s可以消去回车，用这个可以ac。c++里用cin>>同样不用考虑这个问题 for( j=0;j<m;j++ ) { if( map[i][j]=='S' ) { sta.x=i ; sta.y=j ; } } } flag[sta.x][sta.y]=1; if( dfs( 0,sta.x,sta.y ) ) printf( "YES " ); else printf( "NO " ); } return 0; }
优化后的算法时间是260ms
#include<stdio.h> #include<string.h> #include<stdlib.h> char map[10][10]; int flag[10][10]; int way[4][2]={ 0,1,0,-1,1,0,-1,0 }; int n,m; int t,d,ex,ey,sx,sy; int dfs( int s,int x,int y ) { int i,xx,yy; if( map[x][y]=='D' && s==t ) return 1; if( map[x][y]=='D' && s!=t ) return 0; if( s>=t ) return 1; d = abs(x-ex) + abs(y-ey); /*如果预计正常没有墙壁阻隔，那么最短能走多少步*/ if( d + s > t) /*当步数大于要求的步数就返回*/ return 0; if( d % 2 != (t-s) % 2 ) /*因为想要到达目的地，如果中间有阻碍想要跳过再回到最短的线路上就要多走2步 */ return 0; /*所以能到达目的地的步数量一定是d+n*2 所以这个Time一定是和d同奇偶的 而判断下个点有没有偏移正确方向就看到这个点开始能否走到目的地 判断是否能走到 就是看（Time-t）规定步数剩下的步数是否可以到达 就是问这个和d是否同奇偶*/ for( i=0;i<4;i++ ) { xx=x+way[i][0] , yy=y+way[i][1]; if( xx>=0 && xx<n && yy>=0 && yy<m && map[xx][yy]!='X' && !flag[xx][yy] ) { flag[xx][yy]=1; if( dfs(s+1,xx,yy) ) return 1; flag[xx][yy]=0; } } return 0; } int main() { int i,j; while(scanf("%d%d%d",&n,&m,&t)&&(n||m||t)) { memset( flag,0,sizeof(flag) ); for( i=0;i<n;i++ ) { scanf("%s",map[i]);/*最关键的地方*/ for( j=0;j<m;j++ ) { if( map[i][j]=='S' ) { sx=i ; sy=j ; } else if(map[i][j]=='D') { ex=i; ey=j; } } } flag[sx][sy]=1; if( dfs( 0,sx,sy ) ) printf( "YES " ); else printf( "NO " ); } return 0; }