题目描述
希蒙的魔法象棋棋盘(大小n*m)里有一个很奇怪的士,它可以走出九宫格,
并且可以按照原来的规则走(斜着走,左上、右上、左下、右下),
一开始士出现在(x,y),要求你计算出士到达棋盘上任意一个点最少要走几步。
输入格式
输入只有一行四个整数,分别为 n, m, x, y
输出格式
一个n×m 的矩阵,代表士到达某个点最少要走几步
(左对齐,宽 5 格,不能到达则输出 -1)。
输出时需要用到占位符%-5d
样例
输入样例
3 3 1 1
输出样例
0 -1 2
-1 1 -1
2 -1 2
数据范围与提示
对于全部的测试点,保证1≤x≤n≤400,
1≤y≤m≤400。
我的代码:
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
struct Node{
int x,y,step;
};
int vis[505][505];
int n,m,sx,sy;
int dx[4]={1,-1,1,-1};
int dy[4]={1,-1,-1,1};
void bfs(int x,int y){
queue<Node> q;
vis[x][y]=0;
q.push({x,y,0});
while(!q.empty()){
Node t=q.front();
q.pop();
for(int i=0;i<4;i++){
int xx = t.x + dx[i];
int yy = t.y + dy[i];
if(xx>=1 && xx<=n && yy>=1 && yy<=m && vis[xx][yy] == 1){
vis[xx][yy]=t.step+1;
q.push({xx,yy,t.step+1});
}
}
}
int main(){
cin>>n>>m>>sx>>sy;
memset(vis,-1,sizeof(vis));
bfs(sx,sy);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
}
}
return 0;
}