首页 > 代码库 > HDU 2364 (记忆化BFS搜索)
HDU 2364 (记忆化BFS搜索)
题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=2364
题目大意：走迷宫。从某个方向进入某点，优先走左或是右。如果左右都走不通，再考虑向前。绝对不能往后走，即使没走过。
解题思路：
还是一个关键:
每个点可以最多可以走4遍。可以从4个方向到达这个点。所以vis第三维要记录走的方向。
辅助一个route数组，用于当前方向时，应该走相对于正北坐标系的方向（即人看地图的上下左右）。
这样就算迷宫中人的方向不同，但是我们给他标记的数却是统一的，都是以他的方向，先左后右再直走。
如果相对于这个人方向的左右能走，要及时标记，不要再直走了。
最后，边界是指1,n,m，不要把1漏掉。
同时如果选择在Push之前判断是否达终点的话（这种方式可以在找到结果后及时剪枝，比较快）记得再bfs之前特判一下出发点是否已经符合要求。
因为这种方式是不会考虑出发点的。
#include "cstdio"#include "cstring"#include "string"#include "iostream"#include "queue"using namespace std;char map[85][85];int T,n,m,sx,sy,vis[85][85][4],dir[4][2]={-1,0,1,0,0,-1,0,1},route[4][4]={2,3,0,1,3,2,1,0,1,0,2,3,0,1,3,2};struct status{ int x,y,dep,dir; status(int x,int y,int dep,int dir):x(x),y(y),dep(dep),dir(dir) {}};int bfs(int x,int y){ queue<status> Q; for(int i=0;i<4;i++) { vis[x][y][i]=true; Q.push(status(x,y,0,i)); } while(!Q.empty()) { status t=Q.front();Q.pop(); bool direct=true; for(int s=0;s<3;s++) { if(s>=2&&!direct) break; int X=t.x+dir[route[t.dir][s]][0],Y=t.y+dir[route[t.dir][s]][1]; if(X<1||X>n||Y<1||Y>m||map[X][Y]==‘#‘) continue; if(s==0||s==1) direct=false; if(vis[X][Y][route[t.dir][s]]) continue; vis[X][Y][route[t.dir][s]]=true; if(X==1||Y==1||X==n||Y==m) {return t.dep+1;} Q.push(status(X,Y,t.dep+1,route[t.dir][s])); } } return -1;}int main(){ //freopen("in.txt","r",stdin); ios::sync_with_stdio(false); cin>>T; string tt; while(T--) { memset(vis,0,sizeof(vis)); cin>>n>>m; for(int i=1;i<=n;i++) { cin>>tt; for(int j=0;j<tt.size();j++) { map[i][j+1]=tt[j]; if(tt[j]==‘@‘) {sx=i;sy=j+1;} } } if(sx==1||sx==n||sy==1||sy==m) cout<<"0"<<endl; else cout<<bfs(sx,sy)<<endl; }}
| 11903906 | 2014-10-18 17:10:04 | Accepted | 2364 | 0MS | 428K | 1648 B | C++ | Physcal |
HDU 2364 (记忆化BFS搜索)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。