洛谷 1443_马的遍历_bfs

发布于 2019-05-06  903 次阅读


题目描述

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


思路

暴力广搜。。。
输出printf(“%-5d”);


#include 
#include 
using namespace std;
int f[1001][1001],fl[1001][1001];
int dx[9]={0,2,2,-2,-2,1,1,-1,-1};
int dy[9]={0,1,-1,1,-1,2,-2,2,-2};
int n,m;
int bfs(int x,int y)
{
    queue tx;
    queue ty;
    queue state;
    tx.push(x); ty.push(y);
    fl[x][y]=1;
    f[x][y]=0;
    state.push(0);
    while (!tx.empty())
    {
        int xx=tx.front(),yy=ty.front(),s=state.front();
        tx.pop(); ty.pop(); state.pop();
        for (int i=1;i<=8;i++)
            if (xx+dx[i]>=1&&xx+dx[i]<=n&&yy+dy[i]>=1&&yy+dy[i]<=m&&fl[xx+dx[i]][yy+dy[i]]==0)
            {
                fl[xx+dx[i]][yy+dy[i]]=1;
                f[xx+dx[i]][yy+dy[i]]=s+1;
                state.push(s+1);
                tx.push(xx+dx[i]);
                ty.push(yy+dy[i]);
            }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            f[i][j]=-1;
    int x,y;
    scanf("%d%d",&x,&y);
    bfs(x,y);
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=m;j++)
            printf("%-5d",f[i][j]);
        printf("\n");
    }

}
]]>