pku 3083 Children of the Candy Corn DFS+BFS

男娘i 2022-08-09 15:48 25阅读 0赞

两次dfs,一次bfs,貌似数据不是很大0ms过.

不过这一题相当于几道题,代码写的挺长...

难点在于dfs时的走向向判断问题, 我采用的方法是:

方向left, up, right, down分别用0, 1, 2, 3表示.

保存上一次的位置,再根据这一次的位置,判断其方向,然后向左旋转(沿着left走时)或向右向右旋转(沿着right走时),找出其下一步前进的方向.

\#include <iostream> \#include <algorithm> \#include <vector> \#include <queue> using namespace std; int maze\[40\]\[40\]; int w, h; int startx,starty, exitx, exity; int cnt1, cnt2; int dx\[\] = \{-1, 0, 1, 0\}; int dy\[\] = \{0, -1, 0, 1\}; inline int judgeDir1(int x,int y, int dir) \{ if(maze\[y+dy\[(dir-1+4)%4\]\]\[x+dx\[(dir-1+4)%4\]\] == 1 || maze\[y+dy\[(dir-1+4)%4\]\]\[x+dx\[(dir-1+4)%4\]\] == 3) return (dir-1+4)%4; else if(maze\[y+dy\[(dir)%4\]\]\[x+dx\[(dir)%4\]\] == 1 || maze\[y+dy\[(dir)%4\]\]\[x+dx\[(dir)%4\]\] == 3) return (dir)%4; else if(maze\[y+dy\[(dir+1)%4\]\]\[x+dx\[(dir+1)%4\]\] == 1 || maze\[y+dy\[(dir+1)%4\]\]\[x+dx\[(dir+1)%4\]\] == 3) return (dir+1)%4; else return (dir+2)%4; \} inline int judgeDir2(int x,int y, int dir) \{ if(maze\[y+dy\[(dir+1)%4\]\]\[x+dx\[(dir+1)%4\]\] == 1 || maze\[y+dy\[(dir+1)%4\]\]\[x+dx\[(dir+1)%4\]\] == 3) return (dir+1)%4; else if(maze\[y+dy\[(dir)%4\]\]\[x+dx\[(dir)%4\]\] == 1 || maze\[y+dy\[(dir)%4\]\]\[x+dx\[(dir)%4\]\] == 3) return (dir)%4; else if(maze\[y+dy\[(dir-1+4)%4\]\]\[x+dx\[(dir-1+4)%4\]\] == 1 || maze\[y+dy\[(dir-1+4)%4\]\]\[x+dx\[(dir-1+4)%4\]\] == 1) return (dir-1+4)%4; else return (dir-2+4)%4; \} inline int direction(int x, int y, int ox, int oy) \{ if(y == oy && x < ox) return 0; //left else if(x == ox && y < oy) return 1; //up else if(y == oy && ox < x) return 2; //right else return 3; //down \} void dfs1(int x, int y, int ox, int oy, int n) \{ if(x == exitx && y == exity) \{ cnt1 = n+1; return; \} int dir = judgeDir1(x, y, direction(x, y, ox, oy)); if(dir == 0) dfs1(x-1, y, x, y, n+1); else if(dir == 1) dfs1(x, y-1, x, y, n+1); else if(dir == 2) dfs1(x+1, y, x, y, n+1); else dfs1(x, y+1, x, y, n+1); \} void dfs2(int x, int y, int ox, int oy, int n) \{ if(x == exitx && y == exity) \{ cnt2 = n+1; return; \} int dir = judgeDir2(x, y, direction(x, y, ox, oy)); if(dir == 0) dfs2(x-1, y, x, y, n+1); else if(dir == 1) dfs2(x, y-1, x, y, n+1); else if(dir == 2) dfs2(x+1, y, x, y, n+1); else dfs2(x, y+1, x, y, n+1); \} struct Point\{ int x, y; Point(int xx, int yy) \{x = xx; y = yy;\} \}; bool ok(int x, int y) \{ if(x < 0 || x >= w || y < 0 || y >= h) return false; return (maze\[y\]\[x\]==1 || maze\[y\]\[x\] == 3); \} bool visited\[40\]\[40\]; int step\[40\]\[40\]; int bfs(int x, int y) \{ memset(visited, 0, sizeof(visited)); memset(step, 0, sizeof(step)); queue<Point> q; q.push(Point(x, y)); visited\[y\]\[x\] = true; int cnt = 0; while(!q.empty()) \{ Point p = q.front(); if(p.x == exitx && p.y == exity) break; q.pop(); for(int i = 0; i < 4; ++i) \{ int tempx = p.x+dx\[i\], tempy = p.y+dy\[i\]; if(ok(tempx, tempy) && !visited\[tempy\]\[tempx\]) \{ step\[tempy\]\[tempx\] = step\[p.y\]\[p.x\] + 1; q.push(Point(tempx, tempy)); visited\[tempy\]\[tempx\] = true; \} \} \} return step\[exity\]\[exitx\]+1; \} int main() \{ int cnt; char ch; scanf("%d", &cnt); int orgx, orgy; while(cnt--) \{ scanf("%d%d", &w, &h); for (int i = 0; i < h; ++i) for(int j = 0; j < w; ++j) \{ cin >> ch; if(ch == '\#') maze\[i\]\[j\] = 0; else if(ch == '.') maze\[i\]\[j\] = 1; else if(ch == 'S') \{ startx = j, starty = i; maze\[i\]\[j\] = 2; \} else \{ exitx = j, exity = i; maze\[i\]\[j\] = 3; \} \} cnt1 = cnt2 = 0; if(startx == 0) orgx = -1, orgy = starty; else if(startx == w-1) orgx = w, orgy = starty; else if(starty == 0) orgx = startx, orgy = -1; else orgx = startx, orgy = h; dfs1(startx, starty, orgx, orgy, 0); dfs2(startx, starty, orgx, orgy, 0); printf("%d %d %d/n", cnt1, cnt2, bfs(startx, starty)); \} return 0; \}