1. 简单的bfs,有用双向bfs的,但是为了赶进度,以后用双向bfs实现
#include <iostream> #include <fstream> #include <string> #include <algorithm> #include <cstring> #include <stack> #include <queue> using namespace std; int dir[8][2] = {{-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}}; int flag[301][301], step[301][301]; int n, len, i; struct Node { int x, y; } s, t; void bfs() { queue<Node> q; q.push(s); while (!q.empty()) { Node temp = q.front(), nex; flag[temp.x][temp.y] = 1; if (temp.x == t.x && temp.y == t.y) { cout << step[temp.x][temp.y] << endl; return; } q.pop(); for (i = 0; i < 8; i++) { nex.x = temp.x + dir[i][0]; nex.y = temp.y + dir[i][1]; if (nex.x < len && nex.x >= 0 && nex.y < len && nex.y >= 0 && !flag[nex.x][nex.y]) { q.push(nex); step[nex.x][nex.y] = step[temp.x][temp.y] + 1; flag[nex.x][nex.y] = 1; } } } } int main() { cin >> n; while (n--) { cin >> len >> s.x >> s.y >> t.x >> t.y; memset(flag, 0, sizeof(flag)); memset(step, 0, sizeof(step)); step[s.x][s.y] = 0; bfs(); } return 0; }