洛谷P1443 马的遍历(bfs)

谁借莪１个温暖的怀抱￠ 2021-10-18 15:44 356阅读 0赞

[https://www.luogu.org/problem/P1443][https_www.luogu.org_problem_P1443]

思路：马走日字格，它可以走十六个方向,int dir\[8\]\[2\]= \{2,1,1,2,-2,1,-1,2,2,-1,1,-2,-2,-1,-1,-2\}; 将马可以走到的每一步入队列，记录步数

#include <cstdio>
    #include <iostream>
    #include <algorithm>
    #include <cmath>
    #include <queue>
    #include <vector>
    #include <cstring>
    #include <map>
    #define mem(a) memset(a,0,sizeof(a))
    using namespace std;
    typedef long long lll;
    const int maxn = 200005;
    const lll INF = 0x3f3f3f3f3f;
    int dir[8][2]= {
        2,1,1,2,-2,1,-1,2,2,-1,1,-2,-2,-1,-1,-2};
    int dir2[4][2]= {
        0,1,0,-1,1,0,-1,0};
    bool flag;
    int a[1005][1005],b[1005][1005],n,m,sx,sy;
    string s[1005];
    struct node
    {
        int x,y;
        node() {};
        node(int xx,int yy):x(xx),y(yy) {};
    };
    
    void bfs(int x,int y)
    {
        //  cout << 1 <<endl;
        queue<node>q;
        q.push(node(x,y));
    //    b[x][y]=1;
        a[x][y] = 0;
        while(!q.empty())
        {
            node p = q.front();
            q.pop();
            for(int i=0; i<8; i++)
            {
                int fx = p.x + dir[i][0],fy = p.y + dir[i][1];
                if(fx < 1 || fx > n || fy < 1 || fy > m ||a[fx][fy]!=-1||(fx == sx&&fy == sy)) continue;
                q.push(node(fx,fy));
                a[fx][fy] = a[p.x][p.y]+1;
               // b[fx][fy]=1;
            }
        }
    }
    int main()
    {
        memset(a,-1,sizeof(a));
        scanf("%d%d%d%d",&n,&m,&sx,&sy);
        bfs(sx,sy);
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=m; j++)
                printf("%-5d",a[i][j]);
            printf("\n");
        }
        return 0;
    }

转载于:https://www.cnblogs.com/LLLAIH/p/11294079.html

[https_www.luogu.org_problem_P1443]: https://www.luogu.org/problem/P1443