#include<stdio.h> #include<queue> #include<cstdlib> #include<math.h> #include<string.h> #include<algorithm> using namespace std; int a[8][2] = { { -2, -1 }, { -2, 1 }, { -1, 2 }, { 1, 2 }, { 2, 1 }, { 2, -1 }, { 1, -2 }, { -1, -2 } }; int x, y, x1, Y, n; int b[310][310]; struct node { int x; int y; int f; int g; bool operator <(const node &a) const { if (f == a.f) return g>a.g; return f > a.f; } }str, str1; priority_queue<node>Q; int BFS() { if (Q.top().x == x1&&Q.top().y == Y) return 0; while (!Q.empty()) { str = Q.top(); Q.pop(); for (int i = 0; i < 8; i++) { str1 = str; str1.x += a[i][0]; str1.y += a[i][1]; str1.g += 1; str1.f = abs(str1.x - x1) + abs(str1.y - Y)+ str1.g*3; if (str1.x == x1&&str1.y == Y) return str1.g; if (str1.x >= 0 && str1.x < n&&str1.y >= 0 && str1.y < n&&!b[str1.x][str1.y]){ b[str1.x][str1.y] = 1; Q.push(str1); } } } } int main() { int t; scanf("%d", &t); while (t--) { int c = 0; scanf("%d", &n); memset(b, 0, sizeof(b)); scanf("%d%d%d%d", &x, &y, &x1, &Y); while (!Q.empty())Q.pop(); str.x = x; str.y = y; b[str.x][str.y]= 1; str.g = 0; str.f = abs(str.x - x1) + abs(str.y - Y) + str.g * 3; Q.push(str); c = BFS(); printf("%d\n", c); } return 0; } |
Double click to view unformatted code.