首页 > 代码库 > 基础搜索入门(二)
基础搜索入门(二)
HDU_1548 A strange lift
水题。bfs+优先队列。从一个位置到达另一个位置的最少操作数。
代码清单:
#include<queue> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; struct edge { int x; int t; friend bool operator<(edge a,edge b){ return a.t>b.t; } }; int N,A,B; int n[205]; int vis[205]; void bfs() { priority_queue<edge>q; edge p,w; while(q.size()) q.pop(); p.x=A; p.t=0; q.push(p); memset(vis,0x5f,sizeof(vis)); vis[A]=0; int first=1; while(q.size()) { p=q.top(); q.pop(); if(p.x==B){ first=0; printf("%d\n",p.t); break; } w.x=p.x+n[p.x]; w.t=p.t+1; if(w.x>=1&&w.x<=N&&w.t<vis[w.x]) { vis[w.x]=w.t; q.push(w); } w.x=p.x-n[p.x]; if(w.x>=1&&w.x<=N&&w.t<vis[w.x]) { vis[w.x]=w.t; q.push(w); } } if(first) printf("-1\n"); } int main() { while(scanf("%d",&N)!=EOF) { if(N==0) break; scanf("%d%d",&A,&B); for(int i=1;i<=N;i++) scanf("%d",&n[i]); bfs(); }return 0; }
HDU_1728 逃离迷宫
bfs,由于题目只是说能否到达,所以不需要使用优先队列。入队时只要满足转弯数小于当前转弯数即可。
代码清单:
#include<queue> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; struct edge{ int x,y; int pos,turn; }; int T,m,n; int k,x1,y1,x2,y2; char s[105][105]; int vis[105][105]; int xy[4][2]={{0,-1},{-1,0},{0,1},{1,0}}; bool bfs(){ if(x1==x2&&y1==y2) return true; queue<edge>q; while(q.size()) q.pop(); edge p,w; memset(vis,0x5f,sizeof(vis)); vis[y1][x1]=-1; for(int i=0;i<4;i++){ p.x=y1+xy[i][0]; p.y=x1+xy[i][1]; p.pos=i; p.turn=0; if(p.x>=0&&p.x<m&&p.y>=0&&p.y<n&&s[p.x][p.y]!='*') { vis[p.x][p.y]=0; q.push(p); } } while(q.size()){ p=q.front(); q.pop(); if(p.x==y2&&p.y==x2) return true; for(int i=0;i<4;i++){ w.x=p.x+xy[i][0]; w.y=p.y+xy[i][1]; w.pos=i; if(w.pos!=p.pos) w.turn=p.turn+1; else w.turn=p.turn; if(w.x>=0&&w.x<m&&w.y>=0&&w.y<n&&s[w.x][w.y]!='*'&&w.turn<=vis[w.x][w.y]&&w.turn<=k){ vis[w.x][w.y]=w.turn; q.push(w); } } } return false; } int main(){ scanf("%d",&T); while(T--){ scanf("%d%d",&m,&n); for(int i=0;i<m;i++) scanf("%s",s[i]); scanf("%d%d%d%d%d",&k,&x1,&y1,&x2,&y2); x1-=1; y1-=1; x2-=1; y2-=1; if(bfs()) printf("yes\n"); else printf("no\n"); }return 0; }
HDU_1180 诡异的楼梯
bfs+优先队列。注意的是到达楼梯时楼梯的状态可由 当前时间+当前朝向 来判断。
代码清单:
#include<queue> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; struct edge { int x,y; int time; friend bool operator<(edge a,edge b){ return a.time>b.time; } }; int m,n; int sx,sy; int ex,ey; int vis[25][25]; char s[25][25]; int xy[4][2]={{0,-1},{-1,0},{0,1},{1,0}}; void bfs() { priority_queue<edge>q; while(q.size()) q.pop(); edge p,w; memset(vis,0x5f,sizeof(vis)); p.x=sx; p.y=sy; p.time=0; vis[sx][sy]=0; q.push(p); while(q.size()) { p=q.top(); q.pop(); //cout<<p.x<<" "<<p.y<<" "<<p.time<<endl; if(p.x==ex&&p.y==ey) { printf("%d\n",p.time); break; } for(int i=0;i<4;i++) { w.x=p.x+xy[i][0]; w.y=p.y+xy[i][1]; if(s[w.x][w.y]=='|') { w.x+=xy[i][0]; w.y+=xy[i][1]; if(i==1 || i==3) // i 表示当前朝向 { if(p.time%2==0) w.time=p.time+1; else w.time=p.time+2; } else { if(p.time%2==0) w.time=p.time+2; else w.time=p.time+1; } } else if(s[w.x][w.y]=='-') { w.x+=xy[i][0]; w.y+=xy[i][1]; if(i==0 || i==2) { if(p.time%2==0) w.time=p.time+1; else w.time=p.time+2; } else { if(p.time%2==0) w.time=p.time+2; else w.time=p.time+1; } } else w.time=p.time+1; if(w.x>=0&&w.x<m&&w.y>=0&&w.y<n&&s[w.x][w.y]!='*'&&w.time<vis[w.x][w.y]) { vis[w.x][w.y]=w.time; q.push(w); } } } } int main() { while(scanf("%d%d",&m,&n)!=EOF) { for(int i=0;i<m;i++) { scanf("%s",s[i]); for(int j=0;j<n;j++) { if(s[i][j]=='S') { sx=i; sy=j; } if(s[i][j]=='T') { ex=i; ey=j; } } } bfs(); }return 0; }
基础搜索入门(二)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。