题目

https://www.luogu.com.cn/problem/P1443

思路

因为自己老是忘记BFS的模板，写一个模板自己看；一般的BFS题目都可以按照这个代码写

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;

const int maxn = 400 + 10;
struct node{//定义结构体
    int x,y;
    int step;
    friend bool operator<(node a,node b){//重载运算符
        return a.step > b.step;
    }
};
//定义数组
int dist[8][2] = {{1,-2},{2,-1},{2,1},{1,2},{-1,2},{-2,1},{-2,-1},{-1,-2}};
int a[maxn][maxn];
bool vis[maxn][maxn];//定义vis数组
priority_queue<node>Q;//优先队列
int n,m;
int u, v;

void bfs(){
    //初始化第一个结点
    a[u][v] = 0;
    vis[u][v] = 1;
    node e1,e2;
    e1.step = 0;e1.x = u;e1.y = v;
    Q.push(e1);
    while(!Q.empty()){
        e2 = Q.top();Q.pop();
        //if(...){....;break;}
        //遍历
        for(int i=0;i<8;i++){
            int xx = e2.x + dist[i][0];
            int yy = e2.y + dist[i][1];
            if(xx>=1 && xx<=n && yy>=1 && yy<=m && !vis[xx][yy]){
                e1.step = e2.step + 1;
                e1.x = xx;
                e1.y = yy;
                vis[e1.x][e1.y] = 1;
                a[e1.x][e1.y] = e1.step;
                Q.push(e1);
            }
        }

    }
}

int main(){
    scanf("%d %d %d %d",&n, &m, &u, &v);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            a[i][j] = -1;
        }
    }
    bfs();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            printf("%-5d",a[i][j]);
        }
        printf("\n");
    }
    printf("\n");
    return 0;
}