poj 1915 Knight Moves【BFS】【简单】-蒲公英云

poj 1915 Knight Moves【BFS】【简单】

Knight Moves

Time Limit: 1000MS		Memory Limit: 30000K
Total Submissions: 23541		Accepted: 11059

Description

题目大意：输入N，表示棋盘大小为N*N，在输入两个坐标，分别是起始点与目标点，问从起始点到目标点的最少步数【马的行走规则与国际象棋中的一样】，

Sample Input

Sample Output

5
28
0

已Accept代码【c++提交】

#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
int dx[] = {1, 1, -1, -1, 2, 2, -2, -2};
int dy[] = {2, -2, 2, -2, 1, -1, 1, -1};
int n;
int dis[301][301];
int a, b, x, y;
typedef struct node{
    int x, y;
    node() {}
    node(int x, int y) : x(x), y(y) {}
}node;
void BFS() {
    queue <node> Q;
    memset(dis, 0x3f3f3f3f, sizeof(dis));
    Q.push(node(a, b));
    dis[a][b] = 0;
    while(!Q.empty()) {
        node k = Q.front();
        Q.pop();
        int r = k.x;
        int c = k.y;
        int ok = 0;
        for(int i = 0; i < 8; i++) {
            int nx = r + dx[i];
            int ny = c + dy[i];
            if(nx < 0 || nx >=n || ny < 0 || ny >= n)
                continue;
            if(dis[nx][ny] > dis[r][c] + 1) {
                dis[nx][ny] = dis[r][c] + 1;
                Q.push(node(nx, ny));
            }
        }
    }
    printf("%d\n", dis[x][y]);
}
int main() {
    int t;
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        scanf("%d%d%d%d", &a, &b, &x, &y);
        BFS();
    }
    return 0;
}