马的遍历（BFS)-洛谷

洛谷-马的遍历

来源：https://www.luogu.com.cn/problem/P1443

题目描述

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

输入格式

一行四个数据，棋盘的大小和马的坐标

输出格式

一个n*m的矩阵，代表马到达某个点最少要走几步（左对齐，宽5格，不能到达则输出-1）

样例

输入

3 3 1 1

**输出 **

0    3    2    
3    -1   1    
2    1    4    

看到题目第一想法是~

1：马是怎么走的？哈哈哈哈哈。。。

“马”走动的方法是每步一直一斜，即先横着或直着走一格，然后再斜着走一个对角线，俗称“马走日”。在“日”的对角线上两点可以一步到达，其他地方不能到达，如图所示。

	（x-2,y-1）		（x-2,y+1）
（x-1,y-2）				（x-1,y+2）
		(x,y)马
（x+1,y-2）				（x+1,y+2）
	（x+2,y-1）		（x+2,y+1）

2：左对齐，宽5格咋搞，百度即得 printf("%-5d",a);

3：然后想到了广度优先搜索，让我们先来解释一下这种搜索方式。

例如：这棵树

BFS搜索，假设从1开始，然后遍历和1相邻的2,3,4，接着通过2,3,4遍历5 6 7 8 9 10（注意顺序）

实现过程是通过一个队列：（这里通过数组表示的队列）

1	2	3	4	5	6	7	8	9	10
1	2	3	4	5	6	7	8	9	10
1	2	3	4	5	6	7	8	9	10

当头指针等于尾指针时，遍历完毕，或者说符合条件的点，已经遍历完毕。

1	2	3	4	5	6	7	8	9	10
1	2	3	4	5	6	7	8	9	10
1	2	3	4	5	6	7	8	9	10

我们可以发现每一次的遍历都离原始点1是相同的距离，所以当我们做某些最短路径的题时候，可以考虑一下bfs。

先来一个模板：

BFS模板（广度优先搜索）

void bfs()
{
	 初始化，初始状态存数组; 
	 int head=0,tail=1，que[max_size];//构建队列
	 标记初始点 
	 while(head<tail)
	 {
	 	head++;//指向待扩展结点
		for(i=1;i<=maxi;++i)
		{
			if(满足条件||不重复)
			{
				tail++;
				将新节点存入队列
			}	
		}
	}
}

具体操作：

1：选择一个二维数组res[] [],先全部赋值为-1，里面存放到最终结果（棋盘上每一点的最短步数）

2： 用一个结构体数组a来表示马所在的位置，并充当BFS模板的队列，head,tail,充当队列的头尾指针

3：两个数组x[],y[]联合表示马可以到达的八个位置，用于判断是否符合条件，然后就是要注意在判断的时候不要越界就好啦。

然后是不是感觉来了，那就自己先试一试吧，万一就AC了呢。

完整代码：

 #include<bits/stdc++.h>
int n,m,nx,ny;  
int res[405][405];//res表示最终输出结果，下标代表棋盘位置，值代表最少步数 
int x[8]={1,2,-1,-2,-1,-2,1,2};
int y[8]={2,1,2,1,-2,-1,-2,-1};

struct queue{
	int x,y;
}a[40010];//构建bfs的队列（用数组表示） 

void bfs(int i,int j)
{
     int head=1,tail=2; 
     a[2].x=i,a[2].y=j;
	 res[i][j]=0;//初始位置的最少步数为0 
     while(head<tail)
	 {
        head++;
        for(int q=0;q<8;q++)
		{
			//(xx,yy)表示目前马走到的位置，还有。。。~~变量名真的好难取~~  
            int xx=a[head].x+x[q]; 
            int yy=a[head].y+y[q];
             
            if((res[xx][yy]==-1) && xx>=1 && xx<=n && yy>=1 && yy<=m)//判断是否走过，是否越界 
			{
                tail++;
                res[xx][yy]=res[a[head].x][a[head].y]+1;//最少步数加一 
                a[tail].x=xx;
                a[tail].y=yy;
            }
        }
    }
}

int main()
{
	
    scanf("%d%d%d%d",&n,&m,&nx,&ny);
    memset(res,-1,sizeof res);
    bfs(nx,ny);
    
    for(int i=1;i<=n;i++)
	{
        for(int j=1;j<=m;j++)
		{
			printf("%-5d",res[i][j]);
        }
        printf("\n");
    }
}

欢迎大家友好评论呀，有啥问题dd我呀。