题目描述
有一个?n \times mn×m?的棋盘，在某个点?(x, y)(x,y)?上有一个马，要求你计算出马到达棋盘上任意一个点最少要走几步。
输入格式
输入只有一行四个整数，分别为?n, m, x, yn,m,x,y。
输出格式
一个 n×m?的矩阵，代表马到达某个点最少要走几步（左对齐，宽?5格，不能到达则输出?-1 ）。
输入输出样例
输入
3 3 1 1
输出
0 3 2
3 -1 1
2 1 4
说明/提示
数据规模与约定
对于全部的测试点，保证4001≤x≤n≤400，4001≤y≤m≤400。
#include <iostream>
#include <cstring>
#include <queue>
#include <cstdio>//用printf时要加
using namespace std;
queue<pair<int, int> > q;//多打一个空格在> >里面
int f[500][500];
bool vis[500][500];
int n, m, x, y;
int dx[8] = {-1, -2, -2, -1, 1, 2, 2, 1};
int dy[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int main(){
cin >> n >> m >> x >> y;
memset(vis, false, sizeof(vis));
memset(f, -1, sizeof(f));
q.push(make_pair(x, y));
vis[x][y] = true;
f[x][y] = 0;
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];
int v = yy + dy[i];
if(u >= 1 && u <= n && v >= 1 && v <= m && !vis[u][v]){
vis[u][v] = true;
q.push(make_pair(u, v));
f[u][v] = f[xx][yy] + 1;
}
}
}
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= m; j ++)
printf("%-5d", f[i][j]);
cout << endl;
}
return 0;
}
?
|