洛谷P1443 马的遍历【BFS】

题目描述

有一个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

思路：这种题的话用宽搜和广搜都可以，我的思路是每次读取它周围的（能到达的八个方向），在边界内并且未到达过的点入队列，入队的继续读取，不过步数要加一。

#include<cstdio>

#include<queue>

#include<cstring>

#include<iostream>

using namespace std;

const int maxn=405;

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

int n,m,x,y;

int m1[405][405],mark[405][405];

struct node

{

    int a,b;

};

void bfs(int t)

{

    node f;

    queue <node> q;

    f.a=x,f.b=y;

    q.push(f);

    while(!q.empty())

    {

        node front =q.front();

        q.pop();

        for(int i=0;i<8;++i)

        {

            int dx=front.a+d[0][i];

            int dy=front.b+d[1][i];

            if(dx>0 && dx<=n && dy>0 && dy <=m && !mark[dx][dy])

            {

                mark[dx][dy]=1;

                m1[dx][dy]=m1[front.a][front.b]+1;

                node n1;

                n1.a=dx,n1.b=dy;

                q.push(n1);

            }

        }

    }

}

int main()

{

    scanf("%d%d%d%d",&n,&m,&x,&y);

    memset(m1,-1,sizeof(m1));

    m1[x][y]=0;

    bfs(1);

    m1[x][y]=0;

    for(int i=1;i<=n;++i)

    {

        for(int j=1;j<=m;++j)

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

        printf("\n");

    }

    //printf("%d\n",m1[1][1]);

    return 0;

}

巴特西

洛谷P1443 马的遍历【BFS】

题目描述

输入输出格式

输入输出样例

最新文章

热门文章