首页 > 代码库 > UVA - 1601 - The Morning after Halloween
UVA - 1601 - The Morning after Halloween
题目链接：点击这里
题目大意：
给出一个迷宫，在迷宫中有用小写字母表示的几个精灵，
有用大写字母表示的对应精灵的目标位置。
问最少需要进行多少次移动可以到达目标位置。
题目分析：
这道题有两种做法。
第一种做法，优化后的BFS搜索。
首先我们先通过给出的迷宫，提取出空格（即可走的路径），
建立新的图，用邻接表把新的图保存下来，这样就不用判断每个移动点是否
是空格位置还是‘#’位置。然后根据这个邻接表，进行BFS搜索。
还有两点值得注意
1.是当前位置的储存，可以通过二进制的方法将三个点的位置ID保存在一个数里面，需要的时候再进行解码。
2.将每个点的位置用ID保存下来，直接通过ID查取对应坐标（即代码所用的邻接表）。
第二种做法，双向BFS搜索。
双向BFS适用于目标位置和起始位置固定的搜索。
改搜索可以有效的降低实际复杂度。
不过需要注意的是，每次搜索需要以层位单位进行搜索，一次将相同深度的状态枚举干净。
给出代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <vector> 5 #include <string> 6 #include <queue> 7 #include <algorithm> 8 using namespace std; 9 inline int getID(int a,int b,int c) 10 { 11 return (a<<16)|(b<<8)|c; 12 } 13 inline bool confict(int a1,int b1,int a2,int b2) 14 { 15 return ((a2==b2)||(a1==b2&&b1==a2)); 16 } 17 int dis[210][210][210]; 18 int dx[] = {0, -1, 1, 0, 0}; 19 int dy[] = {0, 0, 0, -1, 1}; 20 int deg[210]; 21 int to[210][210]; 22 int st[5]; 23 int ed[5]; 24 char s[20][20]; 25 int w,h,n; 26 int bfs() 27 { 28 queue<int> q; 29 q.push(getID(st[0], st[1], st[2])); 30 dis[st[0]][st[1]][st[2]] = 0; 31 while(!q.empty()) 32 { 33 int u=q.front(); 34 q.pop(); 35 int a = (u >> 16) & 0xff, b = (u >> 8) & 0xff, c = u & 0xff; 36 // cout<<a<<" "<<b<<" "<<c<<endl; 37 if(a==ed[0]&&b==ed[1]&&c==ed[2]) 38 return dis[a][b][c]; 39 for(int i=0;i<deg[a];i++) 40 { 41 int a1=to[a][i]; 42 for(int j=0;j<deg[b];j++) 43 { 44 int b1=to[b][j]; 45 if(confict(a,b,a1,b1)) 46 continue; 47 for(int k=0;k<deg[c];k++) 48 { 49 // cout<<i<<" "<<j<<" "<<k<<" *"<<endl; 50 int c1=to[c][k]; 51 if(confict(a,c,a1,c1)||confict(b,c,b1,c1)) 52 continue; 53 if(dis[a1][b1][c1]==-1) 54 { 55 q.push(getID(a1,b1,c1)); 56 dis[a1][b1][c1]=dis[a][b][c]+1; 57 } 58 } 59 } 60 } 61 } 62 return -1; 63 } 64 int main() 65 { 66 while(~scanf("%d%d%d\n",&w,&h,&n)&&n) 67 { 68 for(int i = 0; i < h; i++) 69 { 70 fgets(s[i], 20, stdin); 71 // cout<<i<<endl; 72 } 73 int cnt=0,x[210],y[210],id[21][21]; 74 for(int i=0;i<h;i++) 75 for(int j=0;j<w;j++) 76 if(!(s[i][j]==‘#‘)) 77 { 78 x[cnt]=i; 79 y[cnt]=j; 80 id[i][j]=cnt; 81 if(islower(s[i][j])) 82 st[s[i][j]-‘a‘]=cnt; 83 else if(isupper(s[i][j])) 84 ed[s[i][j]-‘A‘]=cnt; 85 cnt++; 86 } 87 for(int i=0;i<cnt;i++) 88 { 89 deg[i]=0; 90 for(int j=0;j<5;j++) 91 { 92 int nx=x[i]+dx[j]; 93 int ny=y[i]+dy[j]; 94 if(!(s[nx][ny]==‘#‘)) 95 { 96 to[i][deg[i]++]=id[nx][ny]; 97 } 98 } 99 }100 if(n <= 2) { deg[cnt] = 1; to[cnt][0] = cnt; st[2] = ed[2] = cnt++; }101 if(n <= 1) { deg[cnt] = 1; to[cnt][0] = cnt; st[1] = ed[1] = cnt++; }102 memset(dis,-1,sizeof(dis));103 printf("%d\n",bfs());104 }105 return 0;106 }
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <vector> 5 #include <string> 6 #include <queue> 7 #include <algorithm> 8 using namespace std; 9 inline int getID(int a,int b,int c) 10 { 11 return (a<<16)|(b<<8)|c; 12 } 13 inline bool confict(int a1,int b1,int a2,int b2) 14 { 15 return ((a2==b2)||(a1==b2&&b1==a2)); 16 } 17 int dis[210][210][210]; 18 int mark[210][210][210]; 19 int dx[] = {0, -1, 1, 0, 0}; 20 int dy[] = {0, 0, 0, -1, 1}; 21 int deg[210]; 22 int to[210][210]; 23 int st[5]; 24 int ed[5]; 25 char s[20][20]; 26 int w,h,n; 27 int bfs() 28 { 29 queue<int> q1; 30 queue<int> q2; 31 q1.push(getID(st[0], st[1], st[2])); 32 q2.push(getID(ed[0], ed[1], ed[2])); 33 dis[st[0]][st[1]][st[2]] = 0; 34 dis[ed[0]][ed[1]][ed[2]] = 1; 35 mark[st[0]][st[1]][st[2]]=1; 36 mark[ed[0]][ed[1]][ed[2]]=2; 37 while(!q1.empty()||q2.empty()) 38 { 39 int t1=q1.size(); 40 int t2=q2.size(); 41 while(t1--) 42 { 43 int u=q1.front(); 44 q1.pop(); 45 int a = (u >> 16) & 0xff, b = (u >> 8) & 0xff, c = u & 0xff; 46 // cout<<a<<" "<<b<<" "<<c<<endl; 47 //if(a==ed[0]&&b==ed[1]&&c==ed[2]) 48 // return dis[a][b][c]; 49 for(int i=0; i<deg[a]; i++) 50 { 51 int a1=to[a][i]; 52 for(int j=0; j<deg[b]; j++) 53 { 54 int b1=to[b][j]; 55 if(confict(a,b,a1,b1)) 56 continue; 57 for(int k=0; k<deg[c]; k++) 58 { 59 // cout<<i<<" "<<j<<" "<<k<<" *"<<endl; 60 int c1=to[c][k]; 61 if(confict(a,c,a1,c1)||confict(b,c,b1,c1)) 62 continue; 63 if(mark[a1][b1][c1]==0) 64 { 65 q1.push(getID(a1,b1,c1)); 66 dis[a1][b1][c1]=dis[a][b][c]+1; 67 mark[a1][b1][c1]=1; 68 } 69 else if(mark[a1][b1][c1]==2) 70 { 71 return dis[a][b][c]+dis[a1][b1][c1]; 72 } 73 } 74 } 75 } 76 } 77 while(t2--) 78 { 79 int u=q2.front(); 80 q2.pop(); 81 int a = (u >> 16) & 0xff, b = (u >> 8) & 0xff, c = u & 0xff; 82 // cout<<a<<" "<<b<<" "<<c<<endl; 83 //if(a==ed[0]&&b==ed[1]&&c==ed[2]) 84 // return dis[a][b][c]; 85 for(int i=0; i<deg[a]; i++) 86 { 87 int a1=to[a][i]; 88 for(int j=0; j<deg[b]; j++) 89 { 90 int b1=to[b][j]; 91 if(confict(a,b,a1,b1)) 92 continue; 93 for(int k=0; k<deg[c]; k++) 94 { 95 // cout<<i<<" "<<j<<" "<<k<<" *"<<endl; 96 int c1=to[c][k]; 97 if(confict(a,c,a1,c1)||confict(b,c,b1,c1)) 98 continue; 99 if(mark[a1][b1][c1]==0)100 {101 q2.push(getID(a1,b1,c1));102 dis[a1][b1][c1]=dis[a][b][c]+1;103 mark[a1][b1][c1]=2;104 }105 else if(mark[a1][b1][c1]==1)106 {107 return dis[a][b][c]+dis[a1][b1][c1];108 }109 }110 }111 }112 }113 }114 return -1;115 }116 int main()117 {118 while(~scanf("%d%d%d\n",&w,&h,&n)&&n)119 {120 for(int i = 0; i < h; i++)121 {122 fgets(s[i], 20, stdin);123 // cout<<i<<endl;124 }125 int cnt=0,x[210],y[210],id[21][21];126 for(int i=0; i<h; i++)127 for(int j=0; j<w; j++)128 if(!(s[i][j]==‘#‘))129 {130 x[cnt]=i;131 y[cnt]=j;132 id[i][j]=cnt;133 if(islower(s[i][j]))134 st[s[i][j]-‘a‘]=cnt;135 else if(isupper(s[i][j]))136 ed[s[i][j]-‘A‘]=cnt;137 cnt++;138 }139 for(int i=0; i<cnt; i++)140 {141 deg[i]=0;142 for(int j=0; j<5; j++)143 {144 int nx=x[i]+dx[j];145 int ny=y[i]+dy[j];146 if(!(s[nx][ny]==‘#‘))147 {148 to[i][deg[i]++]=id[nx][ny];149 }150 }151 }152 if(n <= 2)153 {154 deg[cnt] = 1;155 to[cnt][0] = cnt;156 st[2] = ed[2] = cnt++;157 }158 if(n <= 1)159 {160 deg[cnt] = 1;161 to[cnt][0] = cnt;162 st[1] = ed[1] = cnt++;163 }164 memset(dis,0,sizeof(dis));165 memset(mark,0,sizeof(mark));166 printf("%d\n",bfs());167 }168 return 0;169 }
UVA - 1601 - The Morning after Halloween
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。