CSP/信奥赛C++刷题训练：经典广搜例题（1）：洛谷P1443 ：马的遍历

CSP/信奥赛C++刷题训练：经典广搜例题（1）：洛谷P1443 ：马的遍历

题目描述

有一个 $n\times m$ 的棋盘，在某个点 $(x,y)$ 上有一个马，要求你计算出马到达棋盘上任意一个点最少要走几步。

输入格式

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

输出格式

一个 $n\times m$ 的矩阵，代表马到达某个点最少要走几步（不能到达则输出 $-1$）。

样例 #1

样例输入 #1

3 3 1 1

样例输出 #1

0    3    2    
3    -1   1    
2    1    4

提示

数据规模与约定

对于全部的测试点，保证 $1\le x\le n\le 400$，$1\le y\le m\le 400$。

使用广搜解题

#include<bits/stdc++.h>
using namespace std;
int n,m,x,y; 
int a[410][410];//棋盘
int b[410][410];//最少步数
int q[160010][2];//队列 
int dx[8]={-2,-2,-1,1,2,2,1,-1};
int dy[8]={-1,1,2,2,1,-1,-2,-2}; 
void bfs(int x,int y){
	int head=1,tail=1;
	q[1][0]=x;//起点入队 
	q[1][1]=y; 
	a[x][y]=1;//标记起点走过
	b[x][y]=0;//起点步数为0
	while(head<=tail){
		int nowx=q[head][0];//当前点 
		int nowy=q[head][1];
		for(int i=0;i<=7;i++){
			int nx=nowx+dx[i];//新点 
			int ny=nowy+dy[i];
			if(nx>=1 && nx<=n && ny>=1 && ny<=m && a[nx][ny]==0){
				tail++;
				q[tail][0]=nx;//新点入队 
				q[tail][1]=ny;
				a[nx][ny]=1;//标记新点走过
				b[nx][ny]=b[nowx][nowy]+1;//更新步数 
			}
		}
		head++;//队首出队 
	} 
}
int main(){
	cin>>n>>m>>x>>y;
	memset(b,-1,sizeof(b));//初始化b数组
	bfs(x,y);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cout<<b[i][j]<<" ";
		}
		cout<<endl;
	} 
	return 0;
} 

文末彩蛋：

点击王老师青少年编程主页有更多精彩内容