题目描述

广度优先搜索bfs;  模板题

算法1

C++ 代码

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
const int INF=0x3f3f3f;
const int N=310;
int n;
bool st[N][N];
int dist[N][N];

int dx[8]={-2,-1,1,2,2,1,-1,-2},dy[8]={1,2,2,1,-1,-2,-2,-1};

void bfs(PII start,PII end){
    memset(st,false,sizeof(st));
    memset(dist,INF,sizeof(dist));

    queue<PII> q;
    dist[start.x][start.y]=0;
    st[start.x][start.y]=true;
    q.push(start);
    while(q.size()){
        PII t=q.front();q.pop();
        int a=t.x,b=t.y;
        for(int i=0;i<8;i++){
            int nx=a+dx[i],ny=b+dy[i];
            if(nx<0||nx>=n||ny<0||ny>=n||st[nx][ny]){continue;}
            if(dist[nx][ny]>dist[a][b]+1){
                dist[nx][ny]=dist[a][b]+1;
                st[nx][ny]=true;
                q.push({nx,ny});
            }
        }
    }
}


int main(){
    int t;
    cin>>t;
    while(t--){
      cin>>n;
      PII start,end;
      cin>>start.x>>start.y;
      cin>>end.x>>end.y;
      bfs(start,end);
      cout<<dist[end.x][end.y]<<endl;
    }

    return 0;
}