pku 1915 Knight Moves 双向BFS

拼搏现实的明天。 2022-08-18 10:55 106阅读 0赞

最简单的双向BFS, 就不做注释和说明了-\_-

\#include <stdio.h> \#include <iostream> \#include <string.h> \#include <queue> using namespace std; struct Point\{ int x, y; Point(int \_x, int \_y)\{x = \_x; y = \_y;\} \}; int startx, starty, endx, endy; int n; int visit\[2\]\[300\]\[300\]; int dx\[\] = \{-2, -1, 1, 2, 2, 1, -1, -2\}; int dy\[\] = \{-1, -2, -2, -1, 1, 2, 2, 1\}; inline bool ok(int x, int y) \{ if(x < 0 || x >= n || y < 0 || y >= n) return false; return true; \} int bfs() \{ queue<Point> q\[2\]; q\[0\].push(Point(startx, starty)); q\[1\].push(Point(endx, endy)); visit\[0\]\[starty\]\[startx\] = visit\[1\]\[endy\]\[endx\] = 0; while(!q\[0\].empty() && !q\[1\].empty()) \{ if(!q\[0\].empty()) \{ Point p = q\[0\].front(); q\[0\].pop(); for(int i = 0; i < 8; ++i) \{ int tempx = p.x + dx\[i\], tempy = p.y + dy\[i\]; if(ok(tempx, tempy) && visit\[0\]\[tempy\]\[tempx\] == -1) \{ if(visit\[1\]\[tempy\]\[tempx\] >= 0) return visit\[0\]\[p.y\]\[p.x\]+visit\[1\]\[tempy\]\[tempx\]+1; q\[0\].push(Point(tempx, tempy)); visit\[0\]\[tempy\]\[tempx\] = visit\[0\]\[p.y\]\[p.x\]+1; \} \} \} if(!q\[1\].empty()) \{ Point p = q\[1\].front(); q\[1\].pop(); for(int i = 0; i < 8; ++i) \{ int tempx = p.x + dx\[i\], tempy = p.y + dy\[i\]; if(ok(tempx, tempy)&& visit\[1\]\[tempy\]\[tempx\] == -1) \{ if(visit\[0\]\[tempy\]\[tempx\] >= 0) return visit\[1\]\[p.y\]\[p.x\]+visit\[0\]\[tempy\]\[tempx\]+1; q\[1\].push(Point(tempx, tempy)); visit\[1\]\[tempy\]\[tempx\] = visit\[1\]\[p.y\]\[p.x\]+1; \} \} \} \} return -1; \} int main() \{ int N; scanf("%d", &N); while (N--) \{ scanf("%d", &n); scanf("%d%d", &starty, &startx); scanf("%d%d", &endy, &endx); if(startx == endx && starty == endy) \{ printf("0/n"); continue; \} memset(visit, -1, sizeof(visit)); printf("%d/n", bfs()); \} return 0; \}