题目地址: http://acm.hdu.edu.cn/showproblem.php?pid=1010
灰常囧的一晚,贡献了两个TLE。
两个剪枝(还没做的,先做一下再看吧,白色字体,看前刮一刮) :
★★ 剪枝一: 如果剩余的可以走的空间有sum个,而T>sum,那么永远无法到达。
★★ 剪枝二: 如果S走到D需要奇数步,而T是偶数,那么永远无法在第T步到达(反之也一样) 。
囧囧更健康:
★ 囧、轻题了,而且还是做过的题(木有印象了)。。。 看过的人挺多,木有细想。。。直接上DFS。。。 贡献了第一个TLE。。。
★ 还是没细想,觉得挂的很奇怪。。。上启发式搜索,我不相信它还敢挂。。。 结果,囧, 又贡献了一个TLE。。。
★ 想到了【剪枝一】,于是添上,515 MS 撸过。。。
★ 回寝路上,突然想到了【剪枝二】,大叹:平时都能想到的,今晚怎么木有想到!回寝室后加上,轻松 0 MS 。。。
★ 突然对剪枝来了兴趣,把【剪枝一】去掉,437 MS 撸过。。。
★ 然后想到你们应该是咋过了的,把启发式去掉,【剪枝一】和【剪枝二】同时添上,果然 78 MS 就 撸了。。
★ 当然,如果单独只用【剪枝一】或者【剪枝二】其中之一,肯定要 TLE 的。。。
==========================================================================================================
非启发式(78 MS):
#include<iostream> #include<cstdio> using namespace std; char map[10][10]; int fx[4]={1,0,0,-1}; int fy[4]={0,1,-1,0}; int n,m; int dfs(int x,int y,int t){ for(int k=0;k<4;k++){ // 4个方向行走 int nx=x+fx[k]; int ny=y+fy[k]; if(nx<0 || nx>=n || ny<0 || ny>=m) continue; if(t==1) // 最后一步如果能到D,则返回1,否则,就不用再继续走了 if(map[nx][ny]=='D') return 1; else continue; if(map[nx][ny]!='.') continue; // 只有 '.' 才能够行走 map[nx][ny]='X'; if(dfs(nx,ny,t-1)) return 1; map[nx][ny]='.'; } return 0; } int main(){ int x,y,t,sum,zx,zy; while(~scanf("%d%d%d",&n,&m,&t)){ if(!n) break; sum=1; for(int i=0;i<n;i++){ scanf("%s",map[i]); for(int j=0;j<m;j++) if(map[i][j]=='S') map[i][j]='X',x=i,y=j; else if(map[i][j]=='D') zx=i,zy=j; else if(map[i][j]=='.') sum++; } // 两个剪枝先判断,无法在T时刻到达,直接NO if(t>sum || (zx-x+zy-y+t)&1) puts("NO"); else if(dfs(x,y,t)) puts("YES"); else puts("NO"); } return 0; } /* 6 6 34 S..... ...... ...... ...... .....X .....D */
==========================================================================================================
启发式搜索(0 MS )
#include<iostream> #include<cstdio> #include<cstring> using namespace std; char map[10][10]; int fx[4]={1,0,0,-1}; int fy[4]={0,1,-1,0}; int n,m,zx,zy; struct Node{ int x,y; Node(){} Node(int a,int b){x=a,y=b;} }que[100]; int bfs(int x,int y){ int s,t,k,nx,ny; int vis[7][7]; memset(vis,-1,sizeof(vis)); que[s=t=0]=Node(x,y); vis[x][y]=0; while(s<=t){ Node no=que[s++]; for(k=0;k<4;k++){ nx=no.x+fx[k]; ny=no.y+fy[k]; if(nx<0 || nx>=n || ny<0 || ny>=m) continue; if(map[nx][ny]=='X' ||vis[nx][ny]!=-1 ) continue; vis[nx][ny]=vis[no.x][no.y]+1; if(map[nx][ny]=='D') return vis[nx][ny]; que[++t]=Node(nx,ny); } } return vis[zx][zy]; } int dfs(int x,int y,int t){ int h=bfs(x,y); if(h==-1 || h>t) return 0; if(h==t) return 1; for(int k=0;k<4;k++){ int nx=x+fx[k]; int ny=y+fy[k]; if(nx<0 || nx>=n || ny<0 || ny>=m) continue; if(map[nx][ny]!='.') continue; map[nx][ny]='X'; if(dfs(nx,ny,t-1)) return 1; map[nx][ny]='.'; } return 0; } int main(){ int x,y,t,sum=0; while(~scanf("%d%d%d",&n,&m,&t)){ if(!n) break; sum=1; for(int i=0;i<n;i++){ scanf("%s",map[i]); for(int j=0;j<m;j++) if(map[i][j]=='S') map[i][j]='X',x=i,y=j; else if(map[i][j]=='D') zx=i,zy=j; else if(map[i][j]=='.') sum++; } if(t>sum || (zx-x+zy-y+t)&1) puts("NO"); else if(dfs(x,y,t)) puts("YES"); else puts("NO"); } return 0; } /* 6 6 34 S..... ...... ...... ...... .....X .....D */