洛谷P1443 马的遍历

佚名 6年前 (2019-04-08) 随笔 1470人围观抢沙发百度已收录

马的遍历

题目链接

LITTLESUN还是太菜了，说好要23：30之前睡觉，结果写锅了调到了现在qwq
这道题对于刚学bfs来说还是有不少可圈可点的的思路
+dx+循环的使用可以大大减少代码量，不过一定记得初始值第一位为0。还有这道题如果不知道马走日就恐怕写不出来了啊。
+给表格初始值直接赋为-1这样少去了标记数组。
+在结构体中增加了step可以直接进行计数。
AC代码如下

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define MAXN 1000
using namespace std;
int n,m;
int G[MAXN][MAXN];
int dx[10] = {0,1,1,-1,-1,2,2,-2,-2};
int dy[10] = {0,2,-2,2,-2,-1,1,-1,1};
struct item
{
    int x;
    int y;
    int step;
};
queue<item>q;
void bfs(item t)
{
    q.push(t);
    while(!q.empty())
    {
        item r;
        r=q.front();
        q.pop();
        for(int i=1;i<=8;i++)
        {
            int x=r.x+dx[i];
            int y=r.y+dy[i];
            if(G[x][y]==-1&&(x>=1&&x<=n)&&(y>=1&&y<=m))
            {
                G[x][y]=r.step+1;
                item t2;
                t2.x=x;
                t2.y=y;
                t2.step=r.step+1;
                q.push(t2);
            }
        }
     } 
}
int main()
{
    int x,y;
    scanf("%d%d%d%d",&n,&m,&x,&y);
//  scanf("%d%d",&n,&m);

//  scanf("%d%d",&x,&y);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            G[i][j]=-1;
        }
    }
    item t;
    t.x=x;
    t.y=y;
    t.step=0;
    G[x][y]=0;
    bfs(t);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            printf("%-5d",G[i][j]);
        }
        cout<<endl;
    }
    
    return 0;
}