首页 > 代码库 > poj3083(Children of the Candy Corn)
poj3083(Children of the Candy Corn)
题目大意：
给你一个由“#” 、“.”、“S”、“E” .构成的图， “#”代表墙不可穿越，“.”代表空白，“S”代表起点，“E”代表重点，问你分别沿着左边走和右边走和最短路径各多少步。
即使这样说，题目还是不太明确，题意还是看不懂，下面简单介绍下具体的走法。
拿第一组测试数据为例子：
######## #......# #.####.# #.####.# #.####.# #.####.# #...#..# #S#E####
左优先 ：由S为起点先向左走，不能走的时候需要右旋转，然后再走自己的左方向，这样以至于自己最大程度的沿着图的左方向走，就一直在自己的方向下左旋转沿着自己的左手边走下去，因为题目说明不会死循环，所以一定能出去。（找出规律：每次相对自己的方向遍历左、上、右、下四个方向）
右优先： 和左优先刚好相反，由S为起点出发，先向右手边走，没路走时做左旋转，再沿着自己的右手边走，直到找到出口。（找出规律：每次相对自己的方向遍历右、上、左、下四个方向）
解题思路：
题意琢磨了好久，最后才搞懂沿着左边和右边的墙走是什么意思。2个DFS+1个BFS、 BFS很简单，简要说下两个BFS怎么建立，因为是每次沿着自己的方向遍历上、下、左、右，这是需要用四个一维数组，把左优先、和右优先的方向存起来，切记沿着自己的方向遍历左优先、右优先。不难发现无论是左优先还是右优先，在自己的方向数组里减一，就是下次遍历左、右优先的起点。左后分别看是否到达了目标位置ex、ey。输出步数总和。
我的代码可能有点长，但是1A。
代码：
1 #include <algorithm> 2 #include <iostream> 3 #include <sstream> 4 #include <cstdlib> 5 #include <cstring> 6 #include <cstdio> 7 #include <string> 8 #include <bitset> 9 #include <vector> 10 #include <queue> 11 #include <stack> 12 #include <cmath> 13 #include <list> 14 //#include <map> 15 #include <set> 16 using namespace std; 17 /***************************************/ 18 #define ll long long 19 #define int64 __int64 20 /***************************************/ 21 const int INF = 0x7f7f7f7f; 22 const double eps = 1e-8; 23 const double PIE=acos(-1.0); 24 const int d1x[]= {0,-1,0,1}; 25 const int d1y[]= {-1,0,1,0}; 26 const int d2x[]= {0,-1,0,1}; 27 const int d2y[]= {1,0,-1,0}; 28 const int fx[]= {-1,-1,-1,0,0,1,1,1}; 29 const int fy[]= {-1,0,1,-1,1,-1,0,1}; 30 /***************************************/ 31 void openfile() 32 { 33 freopen("data.in","rb",stdin); 34 freopen("data.out","wb",stdout); 35 } 36 /**********************华丽丽的分割线,以上为模板部分*****************/ 37 char map[100][100]; 38 int sum1,sum2,sum3; 39 int sum11,sum22; 40 int ex,ey; 41 int w,h; 42 int vis[100][100],cnt[100][100]; 43 44 void zuo(int x,int y,int d) 45 { 46 int i,j; 47 if (x==ex&&y==ey) 48 { 49 sum11=sum1; 50 return ; 51 } 52 if (d==1) 53 d=0; 54 else if (d==2) 55 d=1; 56 else if (d==3) 57 d=2; 58 else if (d==0) 59 d=3; 60 for(i=d;i<4;i++) 61 { 62 if (x+d1x[i]<h&&x+d1x[i]>=0&&y+d1y[i]<w&&y+d1y[i]>=0&&map[x+d1x[i]][y+d1y[i]]!=‘#‘) 63 { 64 sum1++; 65 zuo(x+d1x[i],y+d1y[i],i); 66 } 67 if (sum11) 68 return ; 69 if (i==3) 70 i=-1; 71 } 72 73 74 75 76 /*if (x==ex&&y==ey) 77 return ; 78 if (y-1>=0&&map[x][y-1]==‘.‘) 79 { 80 sum1++; 81 zuo(x,y-1); 82 } 83 else if (x-1>=0&&map[x-1][y]==‘.‘) 84 { 85 sum1++; 86 zuo(x-1,y); 87 } 88 else if (y+1<w&&map[x][y+1]==‘.‘) 89 { 90 sum1++; 91 zuo(x,y+1); 92 } 93 else if (x+1<h&&map[x+1][y]==‘.‘) 94 { 95 sum1++; 96 zuo(x+1,y); 97 } */ 98 } 99 void you(int x,int y,int d) 100 { 101 int i,j; 102 if (x==ex&&y==ey) 103 { 104 sum22=sum2; 105 return ; 106 } 107 if (d==1) 108 d=0; 109 else if (d==2) 110 d=1; 111 else if (d==3) 112 d=2; 113 else if (d==0) 114 d=3; 115 for(i=d;i<4;i++) 116 { 117 if (x+d2x[i]<h&&x+d2x[i]>=0&&y+d2y[i]<w&&x+d2y[i]>=0&&map[x+d2x[i]][y+d2y[i]]!=‘#‘) 118 { 119 sum2++; 120 you(x+d2x[i],y+d2y[i],i); 121 } 122 if (sum22) 123 return ; 124 if (i==3) 125 i=-1; 126 } 127 128 129 130 131 /*if (x==ex&&y==ey) 132 return ; 133 if (y+1>=0&&map[x][y+1]==‘.‘) 134 { 135 sum1++; 136 you(x,y+1); 137 } 138 else if (x-1>=0&&map[x-1][y]==‘.‘) 139 { 140 sum1++; 141 you(x-1,y); 142 } 143 else if (y-1<w&&map[x][y-1]==‘.‘) 144 { 145 sum1++; 146 you(x,y-1); 147 } 148 else if (x+1<h&&map[x+1][y]==‘.‘) 149 { 150 sum1++; 151 you(x+1,y); 152 } */ 153 } 154 int BFS(int x,int y) 155 { 156 queue<int >Q; 157 Q.push(x); 158 Q.push(y); 159 int v1,v2; 160 while(!Q.empty()) 161 { 162 v1=Q.front(); 163 Q.pop(); 164 v2=Q.front(); 165 Q.pop(); 166 if (vis[v1][v2]==-1) 167 continue; 168 if (v1==ex&&v2==ey) 169 { 170 sum3=cnt[v1][v2]; 171 return 0; 172 } 173 vis[v1][v2]=-1; 174 if (v1>=0&&v1<h&&v2>=0&&v2<w) 175 { 176 if (v1-1>=0&&map[v1-1][v2]!=‘#‘) 177 { 178 Q.push(v1-1); 179 Q.push(v2); 180 cnt[v1-1][v2]=cnt[v1][v2]+1; 181 } 182 if (v1+1<h&&map[v1+1][v2]!=‘#‘) 183 { 184 Q.push(v1+1); 185 Q.push(v2); 186 cnt[v1+1][v2]=cnt[v1][v2]+1; 187 } 188 if (v2-1>=0&&map[v1][v2-1]!=‘#‘) 189 { 190 Q.push(v1); 191 Q.push(v2-1); 192 cnt[v1][v2-1]=cnt[v1][v2]+1; 193 } 194 if (v2+1<w&&map[v1][v2+1]!=‘#‘) 195 { 196 Q.push(v1); 197 Q.push(v2+1); 198 cnt[v1][v2+1]=cnt[v1][v2]+1; 199 } 200 } 201 } 202 return 0; 203 } 204 int main() 205 { 206 207 int cas; 208 scanf("%d",&cas); 209 while(cas--) 210 { 211 memset(map,0,sizeof(map)); 212 memset(vis,0,sizeof(vis)); 213 memset(cnt,0,sizeof(cnt)); 214 scanf("%d%d",&w,&h); 215 int i,j; 216 int sx,sy; 217 sum1=0;sum2=0;sum3=0; 218 sum11=0;sum22=0; 219 for(i=0;i<h;i++) 220 { 221 getchar(); 222 for(j=0;j<w;j++) 223 { 224 scanf("%c",&map[i][j]); 225 if (map[i][j]==‘S‘) 226 { 227 sx=i; 228 sy=j; 229 } 230 if (map[i][j]==‘E‘) 231 { 232 ex=i; 233 ey=j; 234 } 235 } 236 } 237 zuo(sx,sy,1); 238 you(sx,sy,1); 239 BFS(sx,sy); 240 printf("%d %d %d\n",sum11+1,sum22+1,sum3+1); 241 } 242 return 0; 243 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。