Knight Moves

题目描述

思路

代码描述

#include <cstdio>
#include <cstring>
#include <queue>

int n,m,ans;
struct Node {
    int x,y,z;
}st,ed,tmp;
std::queue<Node> q;
int mp[305][305];
bool vis[305][305];
int dirx[] = {0,-1,-2,1,2,1};
int diry[] = {0,-2};
bool valid(int x,int y) {
    if (x < 0 || x >= m) return false;
    if (y < 0 || y >= m) return false;
    return true;
}
inline int read() {
    int s = 0,f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') s = s * 10 + ch - '0',ch = getchar();
    return s * f;   
}
int main() {
    n = read();
    while (n--) {
        m = read();
        st.x = read(),st.y = read(),st.z = 0;
        ed.x = read(),ed.y = read();
        tmp.x = st.x,tmp.y = st.y,tmp.z = st.z;
        while (!q.empty()) q.pop();
        memset(vis,sizeof(vis));
        q.push(tmp);
        vis[tmp.x][tmp.y] = true;
        while (!q.empty()) {
            st = q.front();
            q.pop();
            if (st.x == ed.x && st.y == ed.y) {
                ans = st.z; 
                break;
            }
            for (int i = 1; i <= 8; ++i) {
                tmp.x = st.x + dirx[i];
                tmp.y = st.y + diry[i];
                tmp.z = st.z + 1;
                if (valid(tmp.x,tmp.y) && !vis[tmp.x][tmp.y]) {
                    vis[tmp.x][tmp.y] = 1;
                    q.push(tmp);
                }
            }
        }
        printf("%dn",ans);
    }
    return 0;
}