前言 这是一道广搜的题，急的粉丝直接在目录跳到最后一节完整代

目录

题目 题目描述 有一个 �×�n×m 的棋盘，在某个点 (�,�)(x,y) 上有一个马，要求你计算出马到达棋盘上任意一个点最少要走几步。

输入格式 输入只有一行四个整数，分别为 �,�,�,�n,m,x,y。

输出格式   一个 �×�n×m 的矩阵，代表马到达某个点最少要走几步（不能到达则输出 −1−1）。

输入输出样例 输入 #1复制

3 3 1 1 输出 #1复制

0 3 2
3 -1 1
2 1 4
说明/提示 数据规模与约定 对于全部的测试点，保证 1≤�≤�≤4001≤x≤n≤400，1≤�≤�≤4001≤y≤m≤400。

题目讲解 Bfs前的准备 第一步

我们需要讲题目已知条件和输入做好

定义：

const int dx[8] = {-1,-2,-2,-1,1,2,2,1};//方向数组 const int dy[8] = {2,1,-1,-2,2,1,-1,-2};//方向数组 queue<pair<int,int> > q; int n,m,x,y,f[10000][10000],vis[10000][10000];//vis是是否访问过的数 队列可以pair,也可以开结构体

const int dx[8] = {-1,-2,-2,-1,1,2,2,1};//方向数组 const int dy[8] = {2,1,-1,-2,2,1,-1,-2};//方向数组 struct node{ int x,y; }; queue q; int n,m,x,y,f[10000][10000],vis[10000][10000];//vis是是否访问过的数

输入不多说了

cin>>n>>m>>x>>y; BFS分解 第一步：

肯定是把第一个节点塞进队列并且将vis数组的位置标记为走过

f[x][y] = 0;
vis[x][y] = true;
q.push({x,y});

第二步：

我们要开始BFS了，在队列不为空时，我们需要将队头的的元素取出来

while(!q.empty()){
	int xx = q.front().first;
	int yy = q.front().second;
	q.pop();
}

第三步：

我们要向八个方向探索：

while(!q.empty()){
	int xx = q.front().first;
	int yy = q.front().second;
	q.pop();
	for(int i = 0;i<8;++i){
		int u = xx+dx[i],v = yy+dy[i];
	}
}

 第四步：

我们要筛掉不合法的方向，合法的方向将他在vis中标记一下，并且塞进队列

while(!q.empty()){
	int xx = q.front().first;
	int yy = q.front().second;
	q.pop();
	for(int i = 0;i<8;++i){
		int u = xx+dx[i],v = yy+dy[i];
		if(u<1||u>n||v<1||v>m||vis[u][v]) continue;
		vis[u][v] = true;
		q.push({u,v});
		f[u][v] = f[xx][yy]+1;
	}
}

好了，我们就BFS完了

Bfs后的剩余： 我们搜索完了需要输出数组

for(int i=1;i<=n;++i)
	for(int j=1;j<=m;++j)
	{
		cout<<f[i][j]<<" \n"[j==m];
	}

完整代码：

#include <bits/stdc++.h>
using namespace std;

const int dx[8] = {-1,-2,-2,-1,1,2,2,1};//方向数组 

const int dy[8] = {2,1,-1,-2,2,1,-1,-2};//方向数组 

queue<pair<int,int> > q;

int n,m,x,y,f[10000][10000],vis[10000][10000];//vis是是否访问过的数组 

int main()
{
	cin>>n>>m>>x>>y;
	
	f[x][y] = 0;
	
	vis[x][y] = true;
	
	q.push({x,y});
	
	
	while(!q.empty()){
		
		int xx = q.front().first;
		
		int yy = q.front().second;
		
		q.pop();
		
		for(int i = 0;i<8;++i){
			int u = xx+dx[i],v = yy+dy[i];
			
			if(u<1||u>n||v<1||v>m||vis[u][v]) continue;
			
			vis[u][v] = true;
			
			q.push({u,v});
			
			f[u][v] = f[xx][yy]+1;
			
		}
	}
	
	
	
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
		{
			cout<<f[i][j]<<" \n"[j==m];
		}
	return 0;
}