广度优先搜索

JNAzreal

题目是洛谷上面的题目 题名：马的遍历
链接：https://www.luogu.org/problemnew/show/P1443

[C++] 纯文本查看 复制代码

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#define meset(a) memset(a,0,sizeof(a))
int dir[][2]={-1,2,-1,-2,1,2,1,-2,2,1,-2,1,-2,-1,2,-1};
using namespace std;
int mp[500][500],vis[500][500],m,n,dx,dy;
struct node{
    int x,y,step;
    
    bool check()
    {
        if(x>=1&&x<=m&&y>=1&&y<=n)
        {
            if(!vis[x][y])
            return true;
        }
        return false ;
    }
}tail,head;
int main()
{
    cin>>m>>n>>dx>>dy;
    queue<node> q;
    q.push({dx,dy,0});
    vis[dx][dy]=1;
    while(!q.empty())
    {
        head=q.front();
        q.pop();
        for(int i=0;i<8;i++)
        {
            tail=head;
            tail.x+=dir[i][0];
            tail.y+=dir[i][1];
            tail.step++;
            if(tail.check())
            {
                q.push(tail);
                mp[tail.x][tail.y]=tail.step;
                vis[tail.x][tail.y]=1;
            } 
        }
    }
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(mp[i][j]==0)
            mp[i][j]=-1;
            if(i==dx&&j==dy)
            mp[i][j]=0; 
            printf("%-5d",mp[i][j]);
        }
        cout<<endl;
    }
} 

winna

多谢参考了