首页 > 代码库 > POJ 3083 Children of the Candy Corn(顺时针DFS+逆时针DFS+BFS)
POJ 3083 Children of the Candy Corn(顺时针DFS+逆时针DFS+BFS)
题目链接:POJ 3083 Children of the Candy Corn
【题意】给出一个迷宫,不超过40*40,‘#’代表墙,‘.’代表能走,‘S’是起点,‘E’是终点。分别求出从起点一直沿左走,一直沿右走,走到终点所需要的步数。以及走出迷宫的最小步数。
【思路】首先最小步数很简单,一个普通BFS搞定,这道题重点是一直向左走和一直向右走的DFS的方向问题,方向还和游客当时朝向有关。开始一直认为是每次都向左(右)转,直到可以走,然后就一直不对,在google了之后才知道向左走要遵循左上右下的顺时针DFS搜索顺序,向右走要遵循右上左下的逆时针DFS搜索顺序。
具体思路是这样的,这是我画的方向草图:
举个例来说,一直向左,最初的起点由S决定,如果当前位置在1,那么面向的就是3,那么就要先去试探2方向可行否,不行的话就试探3,然后0,最后是1。遵循先向左,不行则顺时针搜索的规则。一直向右边的方法同理,遵循先向右,不行则逆时针搜索的规则。方向的更新按照我定义的是:
nowface = (face + to[i]) % 4;
face是当前朝向,to[i]具体看代码,每回都需要%4,保证数字不超出范围。
【注意】左边、右边优先搜索都不是找最短路,因此走过的路可以再走,无需标记走过的路,并且一旦哪一步确定了走的方向,就不必去搜索其它方向了,按照规则一直搜索下去。
下面贴代码:
1 /* 2 ** POJ 3083 Children of the Candy Corn 3 ** Created by Rayn @@ 2014/05/09 4 ** 这道题重点是left和right的DFS的方向问题,方向还和游客 5 ** 当时朝向有关,BFS就是很普通的最短路搜索 6 ** left搜索要遵循左上右下的顺时针搜索顺序 7 ** right搜索要遵循右上左下的逆时针搜索顺序 8 ** 朝向标记 :左0 上1 右2 下3 9 */ 10 #include <cstdio> 11 #include <cstring> 12 #include <queue> 13 using namespace std; 14 const int MAX = 50; 15 struct pos{ 16 int x, y; 17 int step; 18 }; 19 int left, right; 20 int w, h, sign[MAX][MAX]; 21 char maze[MAX][MAX]; 22 int dir[][2] = {{-1,0},{0,1},{1,0},{0,-1}}; /*0-上,1-右,2-下,3-左*/ 23 24 void leftDFS(int x, int y, int face) 25 { 26 int to[4] = {3,0,1,2}; 27 28 if(maze[x][y] == ‘E‘) 29 { 30 printf("%d ", left); 31 return ; 32 } 33 left++; 34 for(int i=0; i<4; ++i) 35 { 36 int nowface = (face + to[i]) % 4; 37 int tx = x + dir[nowface][0]; 38 int ty = y + dir[nowface][1]; 39 if(tx>=0 && ty>=0 && tx<h && ty<w && maze[tx][ty] != ‘#‘) 40 { 41 leftDFS(tx, ty, nowface); 42 return ; 43 } 44 } 45 } 46 void rightDFS(int x, int y, int face) 47 { 48 int to[4] = {1,0,3,2}; 49 50 if(maze[x][y] == ‘E‘) 51 { 52 printf("%d ", right); 53 return ; 54 } 55 right++; 56 for(int i=0; i<4; ++i) 57 { 58 int nowface = (face + to[i]) % 4; 59 int tx = x + dir[nowface][0]; 60 int ty = y + dir[nowface][1]; 61 if(tx>=0 && ty>=0 && tx<h && ty<w && maze[tx][ty] != ‘#‘) 62 { 63 rightDFS(tx, ty, nowface); 64 return ; 65 } 66 } 67 } 68 void BFS(int x, int y) 69 { 70 queue<pos> q; 71 while(!q.empty()) 72 q.pop(); 73 74 pos start; 75 start.x = x; start.y = y; start.step = 1; 76 q.push(start); 77 sign[x][y] = 1; 78 79 while(!q.empty()) 80 { 81 pos now = q.front(); 82 if(maze[now.x][now.y] == ‘E‘) 83 { 84 printf("%d\n", now.step); 85 return ; 86 } 87 q.pop(); 88 for(int i=0; i<4; ++i) 89 { 90 pos tmp = now; 91 tmp.x = now.x + dir[i][0]; 92 tmp.y = now.y + dir[i][1]; 93 tmp.step = now.step + 1; 94 if(tmp.x>=0 && tmp.y>=0 && tmp.x<h && tmp.y<w && maze[tmp.x][tmp.y] != ‘#‘ && !sign[tmp.x][tmp.y]) 95 { 96 sign[tmp.x][tmp.y] = 1; 97 q.push(tmp); 98 } 99 } 100 } 101 } 102 int main() 103 { 104 int cases; 105 int sx, sy, face; 106 107 scanf("%d", &cases); 108 while(cases--) 109 { 110 memset(sign, 0, sizeof(sign)); 111 112 scanf("%d%d%*c", &w, &h); 113 for(int i=0; i<h; ++i) 114 { 115 scanf("%s", maze[i]); 116 for(int j=0; j<w; ++j) 117 { 118 if(maze[i][j] == ‘S‘) 119 { 120 sx = i; 121 sy = j; 122 } 123 } 124 } 125 //确定初始方位 126 if(sx == 0) 127 face = 2; 128 else if(sx == h-1) 129 face = 0; 130 if(sy == 0) 131 face = 1; 132 else if(sy == w-1) 133 face = 3; 134 135 left = 1; 136 leftDFS(sx, sy, face); 137 right = 1; 138 rightDFS(sx, sy, face); 139 BFS(sx, sy); 140 } 141 return 0; 142 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。