[LUOGU]P1443 马的遍历

有一个n*m的棋盘(1< n,m<=400)，在某个点上有一个马,要求你计算出马到达棋盘上任意一个点最少要走几步

输入输出格式

输入格式：

一行四个数据，棋盘的大小和马的坐标

输出格式：

一个n*m的矩阵，代表马到达某个点最少要走几步（左对齐，宽5格，不能到达则输出-1）

输入输出样例

输入样例#1：

3 3 1 1

输出样例#1：

0 3 2

3 -1 1

2 1 4

基础的宽搜,最后注意输出-1的问题..

我的思路是把除了起始点的0都换成-1

不过memset -1也可以

//Writer:GhostCai && His Yellow Duck

#include<iostream>

#include<cstdio>

#include<queue>

#define MAXN 405

using namespace std;

struct point{

    int x, y;

}node,r;

int a[MAXN][MAXN];

bool vis[MAXN][MAXN];

int m,n,sx,sy;

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

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

void bfs(int x,int y){

    node.x = x;

    node.y = y;

    queue<point> Q;

    vis[x][y]=1;

    a[x][y]=0;

    Q.push(node);

    while(!Q.empty() ){

        r=Q.front();

        Q.pop() ;

        int nx,ny;

        for(int i=0;i<=7;i++){

            nx=r.x + mx[i];

            ny=r.y + my[i];

            if(nx<1||nx>m||ny<1||ny>n) continue;

            if(vis[nx][ny]) continue;

            node.x = nx;

            node.y = ny;

            Q.push(node);

            a[nx][ny]=a[r.x][r.y ] +1;

            vis[nx][ny]=1;

        }

    }

}

int main(){

    cin>>m>>n>>sx>>sy;

    bfs(sx,sy);

    int i,j;

    for(i=1;i<=m;i++){

        for(j=1;j<=n;j++){

            if(a[i][j]==0&&(i!=sx||j!=sy)) a[i][j]=-1;

            printf("%-5d",a[i][j]);

        }

        printf("\n");

    }

}