首页 > 代码库 > uva 816 - Abbott's Revenge(有一点难度的bfs迷宫题目)
uva 816 - Abbott's Revenge(有一点难度的bfs迷宫题目)
就是典型的bfs,但这道题目的难点在于其条件的读取和判断并不简单,需要想办法来读取条件,也需要想办法来判断在每个点处能不能满足向下继续走的条件。
#include<cstdio> #include<cstring> #include<string> #include<queue> #include<iostream> #include<algorithm> using namespace std; struct note { int r; int c; int dir; }; string s,s1; int r0,c0,r1,c1,dir,r2,c2; int has_edge[10][10][4][3]; int d[10][10][4]; note p[10][10][4]; char dirs[]={'N','E','S','W'}; char turns[]={'F','L','R'}; int dr[]={-1,0,1,0}; int dc[]={0,1,0,-1}; note walk(note u,int turn) { note v; int dirr=u.dir; if(turn==1) {dirr=(dirr+3)%4;} if(turn==2) {dirr=(dirr+1)%4;} v.r=u.r+dr[dirr]; v.c=u.c+dc[dirr]; v.dir=dirr; return v; } bool inside(int x,int y) { if(x>=1&&x<=9&&y>=1&&y<=9) return true; return false; } void print_ans(note u) { vector<note> vec; while(1) { if(d[u.r][u.c][u.dir]==0) break; vec.push_back(u); u=p[u.r][u.c][u.dir]; } u.r=r0;u.c=c0;u.dir=dir; vec.push_back(u); cout<<s1<<endl; int cnt=0; for(int i=vec.size()-1;i>=0;i--) { cnt++; if(cnt==1) printf(" "); printf("(%d,%d)",vec[i].r,vec[i].c); if(cnt!=10&&i!=0) printf(" "); if(cnt==10&&i!=0) {printf("\n");cnt=0;} } printf("\n"); } void solve() { queue<note> q; note uu; uu.r=r0;uu.c=c0;uu.dir=dir; note u; u.r=r1;u.c=c1;u.dir=dir; d[r1][c1][dir]=1; p[r1][c1][dir]=uu; d[r0][c0][dir]=0; q.push(u); while(!q.empty()) { u=q.front(); q.pop(); if(u.r==r2&&u.c==c2) {print_ans(u);return;} for(int i=0;i<3;i++) { note v=walk(u,i); if(has_edge[u.r][u.c][u.dir][i]&&inside(v.r,v.c)&&d[v.r][v.c][v.dir]<0) { p[v.r][v.c][v.dir]=u; d[v.r][v.c][v.dir]=d[u.r][u.c][u.dir]+1; q.push(v); } } } cout<<s1<<endl; printf(" No Solution Possible\n"); } int main() { while(cin>>s1) { if(s1=="END") break; memset(has_edge,0,sizeof(has_edge)); memset(d,-1,sizeof(d)); memset(p,0,sizeof(p)); int a,count=0; int a1,a2,dir1,turn1; while(cin>>a) { if(a==0) break; count++; if(count==1) { r0=a; cin>>c0>>s>>r2>>c2; for(int i=0;i<4;i++) { if(s[0]==dirs[i]) { dir=i; break; } } r1=r0+dr[dir]; c1=c0+dc[dir]; } else { a1=a; cin>>a2; while(cin>>s) { if(s[0]=='*') break; for(int i=0;i<4;i++) { if(s[0]==dirs[i]) { dir1=i; break; } } for(int i=1;i<s.size();i++) { for(int j=0;j<3;j++) { if(s[i]==turns[j]) { turn1=j; break; } } has_edge[a1][a2][dir1][turn1]=1; } } } } // for(int i=1;i<=9;i++) // { // for(int j=1;j<=9;j++) // { // for(int k=0;k<4;k++) // { // for(int l=0;l<3;l++) // { // if(has_edge[i][j][k][l]) // printf("[%d][%d][%d][%d]\n",i,j,k,l); // } // } // } // } solve(); } return 0; }
在解决这道题目的过程中,用到了一些很好的处理问题的方法,也包含了一些处理问题的小细节,这种题的解题思想,方法,以及一些细节问题都应该掌握应该掌握。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。