首页 / 更多教程 / bfs两种记录路径方法
bfs两种记录路径方法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了bfs两种记录路径方法,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含3990字,纯文字阅读大概需要6分钟。
内容图文
![bfs两种记录路径方法](/upload/InfoBanner/zyjiaocheng/1182/2a0d190cc63c4add9ff318ca779b4f77.jpg)
#include<cstdio> #include<queue> usingnamespace std; struct sss { int x,y; }ans[6][6]; int map[6][6]; int flag[6][6]; int dec[4][2]={1,0,0,1,-1,0,0,-1}; void print(struct sss q) { if(q.x==0&&q.y==0) { printf("(0, 0)\n"); return; } else { print(ans[q.x][q.y]); printf("(%d, %d)\n",q.x,q.y); } } void bfs(int x,int y) { struct sss q; queue<struct sss> s; flag[0][0]=1; q.x=x; q.y=y; s.push(q); ans[0][0].x=-1; ans[0][0].y=-1; while(!s.empty()) { q=s.front(); s.pop(); if(q.x==4&&q.y==4) { print(q); return; } for(int i=0;i<4;i++) { int xx=dec[i][0]+q.x; int yy=dec[i][1]+q.y; if(xx>=0&&xx<5&&yy>=0&&yy<5&&flag[xx][yy]==0&&map[xx][yy]==0) { struct sss w; w.x=xx; w.y=yy; s.push(w); flag[xx][yy]=1; ans[xx][yy].x=q.x; ans[xx][yy].y=q.y; } } } } int main() { for(int i=0;i<5;i++) { for(int j=0;j<5;j++) { scanf("%d",&map[i][j]); } } bfs(0,0); }
#include<cstdio> #include<cmath> #include<vector> #include<cstring> #include<algorithm> #include<iostream> #include<queue> #include<map> #include<string> usingnamespace std; typedef longlong ll; char mp[1001][1001]; int n,m,k; int flag; int d[1001][1001]; char jg[1000001]; char yx[1000001]; int dis[4][2]={1,0,0,-1,0,1,-1,0}; char str[5]={"DLRU"}; void pan(int x,int y){ //printf("k=%d\n",k);int tmp=k; for(int i=0;i<k;i++){ int dex=-1; for(int j=0;j<4;j++){ pair<int,int> z; z.first=x+dis[j][0]; z.second=y+dis[j][1]; if(z.first>=0&&z.first<n&&z.second>=0&&z.second<m&&mp[z.first][z.second]!=‘*‘&&d[z.first][z.second]<tmp){ dex=j; break; } } tmp--; x=x+dis[dex][0]; y=y+dis[dex][1]; jg[i]=str[dex]; } jg[k]=‘\0‘; printf("%s\n",jg); } void bfs(int x,int y) { queue<pair<int,int> > q; q.push(make_pair(x,y)); for(int i=0;i<1000;i++){ for(int j=0;j<1000;j++) d[i][j]=10000000; } int num=0; d[x][y]=0; while(!q.empty()){ pair<int,int> w=q.front(); q.pop(); num++; for(int i=0;i<4;i++){ pair<int,int> z; z.first=w.first+dis[i][0]; z.second=w.second+dis[i][1]; if(z.first>=0&&z.first<n&&z.second>=0&&z.second<m&&mp[z.first][z.second]==‘.‘){ if(d[z.first][z.second]>d[w.first][w.second]+1){ d[z.first][z.second]=d[w.first][w.second]+1; q.push(z); } } } } /*for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(d[i][j]==10000000) printf("%4d",-1); else printf("%4d",d[i][j]); } printf("\n"); }*/// printf("num=%d\n",num);if(num==1) printf("IMPOSSIBLE"); else pan(x,y); } int main() { scanf("%d%d%d",&n,&m,&k); for(int i=0;i<n;i++){ scanf("%s",mp[i]); } if(k%2){ printf("IMPOSSIBLE"); return0; } int vis=0; for(int i=0;i<n;i++){ for(int j=0;j<m;j++) { if(mp[i][j]==‘X‘) { mp[i][j]=‘.‘; bfs(i,j); vis=1; break; } } if(vis) break; } }
#include<cstdio> #include<queue> using namespace std ; struct sss { int x,y; }ans[ 6 ][ 6 ]; int map [ 6 ][ 6 ]; int flag[ 6 ][ 6 ]; int dec[ 4 ][ 2 ]={ 1 , 0 , 0 , 1 , -1 , 0 , 0 , -1 }; void print (struct sss q) { if (q.x== 0 &&q.y== 0 ) { printf ( "(0, 0)\n" ); return ; } else { print(ans[q.x][q.y]); printf ( "(%d, %d)\n" ,q.x,q.y); } } void bfs (int x,int y) { struct sss q; queue < struct sss> s; flag[ 0 ][ 0 ]= 1 ; q.x=x; q.y=y; s.push(q); ans[ 0 ][ 0 ].x= -1 ; ans[ 0 ][ 0 ].y= -1 ; while (!s.empty()) { q=s.front(); s.pop(); if (q.x== 4 &&q.y== 4 ) { print(q); return ; } for ( int i= 0 ;i< 4 ;i++) { int xx=dec[i][ 0 ]+q.x; int yy=dec[i][ 1 ]+q.y; if (xx>= 0 &&xx< 5 &&yy>= 0 &&yy< 5 &&flag[xx][yy]== 0 && map [xx][yy]== 0 ) { struct sss w; w.x=xx; w.y=yy; s.push(w); flag[xx][yy]= 1 ; ans[xx][yy].x=q.x; ans[xx][yy].y=q.y; } } } } int main () { for ( int i= 0 ;i< 5 ;i++) { for ( int j= 0 ;j< 5 ;j++) { scanf ( "%d" ,& map [i][j]); } } bfs( 0 , 0 ); }
原文:https://www.cnblogs.com/Lis-/p/10572619.html
内容总结
以上是互联网集市为您收集整理的bfs两种记录路径方法全部内容,希望文章能够帮你解决bfs两种记录路径方法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。