2733: 【搜索】【广度优先】 马遍历棋盘
题目描述
有一个n*m的棋盘(1<n,m<=400)，在某个点上有一个马,要求你计算出马到达棋盘上任意一个点最少要走几步
输入
一行四个数据，棋盘的大小和马的坐标
输出
一个n*m的矩阵，代表马到达某个点最少要走几步（左对齐，宽5格，不能到达则输出-1）
样例输入
4 4 1 1
样例输出
0 3 2 5 3 4 1 2 2 1 4 3 5 2 3 2
Code:
#include<bits/stdc++.h>
using namespace std;
struct node{int x,y;
}temp,front;
int dx[4]={1,-1,2,-2};
int dy[4]={1,-1,2,-2};
int a[401][401];
bool vis[401][401];
int n,m;
void bfs(int x,int y,int step){a[x][y]=step;vis[x][y]=true;queue<node>Q;temp.x=x;temp.y=y;Q.push(temp);while(!Q.empty()){front=Q.front();Q.pop();for(int i=0;i<4;i++){for(int j=0;j<4;j++){if(abs(dx[i])!=abs(dy[j])){int nx=front.x+dx[i];int ny=front.y+dy[j];if(nx<1||nx>n||ny<1||ny>m){continue;}if(!vis[nx][ny]){temp.x=nx;temp.y=ny;Q.push(temp);vis[nx][ny]=true;a[nx][ny]=a[front.x][front.y]+1;}}}}}
}
int main(){memset(a,-1,sizeof(a));int x,y;cin>>n>>m>>x>>y;bfs(x,y,0);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){printf("%-5d",a[i][j]);}cout<<endl;}return 0;
}