电商大数据查询平台免费_搜索网站排名_国外免费ip地址_情感营销经典案例

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;//起点步数为0while(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;
} 

文末彩蛋：

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