标程: 广度优先搜索 BFS

àì夳堔傛蜴生んèń 2022-08-09 15:48 152阅读 0赞

贴个标程, 以方便查阅.

\#include <iostream> \#include <algorithm> \#include <vector> \#include <queue> using namespace std; int maze\[40\]\[40\]; int w, h; int startx,starty, exitx, exity; int dx\[\] = \{-1, 0, 1, 0\}; int dy\[\] = \{0, -1, 0, 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; \}

再贴个别人非stl实现的.

\#include <iostream> \#include <string.h> using namespace std; int step\[501\]\[501\]; int visited\[501\]\[501\]; int startx,starty,endx,endy,m,n; struct Node \{ int x; int y; \} que\[250001\]; void bfs() \{ int direct\[8\]\[2\]=\{\{1,2\},\{2,1\},\{-1,-2\},\{-2,-1\},\{-1,2\},\{2,-1\},\{1,-2\},\{-2,1\}\}; int front=-1,rear=-1,curx,cury,tempx,tempy,i; que\[++rear\].x=startx; que\[rear\].y=starty; step\[startx\]\[starty\]=0; visited\[startx\]\[starty\]=1; while(front!=rear) \{ curx=que\[++front\].x; cury=que\[front\].y; if((curx==endx)&&(cury==endy)) break; for(i=0;i<8;i++) \{ tempx=curx+direct\[i\]\[0\]; tempy=cury+direct\[i\]\[1\]; if(tempx>0&&tempx<=m&&tempy>0&&tempy<=n&&visited\[tempx\]\[tempy\]==0) \{ step\[tempx\]\[tempy\]=step\[curx\]\[cury\]+1; visited\[tempx\]\[tempy\]=1; que\[++rear\].x=tempx; que\[rear\].y=tempy; \} \} \} \} int main() \{ int k; cin>>k; while(k--) \{ memset(step,0,sizeof(step)); memset(visited,0,sizeof(visited)); cin>>m>>n; cin>>startx>>starty>>endx>>endy; bfs(); cout<<step\[endx\]\[endy\]<<endl; \} return 0; \}