网站建设与网页设计报告,品牌建设与诚信建设,网站广告是文化事业建设费,政务门户网站建设的意义马的遍历
题目描述
有一个 nmn \times mnm 的棋盘#xff0c;在某个点 (x,y)(x, y)(x,y) 上有一个马#xff0c;要求你计算出马到达棋盘上任意一个点最少要走几步。
输入格式
输入只有一行四个整数#xff0c;分别为 n,m,x,yn, m, x, yn,m,x,y。
输出格式
一个 nmn \t…马的遍历
题目描述
有一个 n×mn \times mn×m 的棋盘在某个点 (x,y)(x, y)(x,y) 上有一个马要求你计算出马到达棋盘上任意一个点最少要走几步。
输入格式
输入只有一行四个整数分别为 n,m,x,yn, m, x, yn,m,x,y。
输出格式
一个 n×mn \times mn×m 的矩阵代表马到达某个点最少要走几步不能到达则输出 −1-1−1。
样例 #1
样例输入 #1
3 3 1 1样例输出 #1
0 3 2
3 -1 1
2 1 4提示
数据规模与约定
对于全部的测试点保证 1≤x≤n≤4001 \leq x \leq n \leq 4001≤x≤n≤4001≤y≤m≤4001 \leq y \leq m \leq 4001≤y≤m≤400。
思路
马走“日”输出格式域宽为5左对齐注意判断是否越界
AC代码
#include iostream
#include queue
#include cstring
#define AUTHOR HEX9CF
using namespace std;const int maxn 405;
const int sun[8][2] {-2, 1, -2, -1, -1, 2, -1, -2, 2, 1, 2, -1, 1, 2, 1, -2};
int n, m, x, y;bool vis[maxn][maxn];
int stp[maxn][maxn];
queuepairint, int q;void bfs(int x, int y)
{vis[x][y] 1;stp[x][y] 0;q.push(make_pair(x, y));while (!q.empty()){pairint, int f q.front();q.pop();for (int i 0; i 8; i){int xx f.first sun[i][0];int yy f.second sun[i][1];if (xx 0 xx n yy 0 yy m !vis[xx][yy]){vis[xx][yy] 1;q.push(make_pair(xx, yy));stp[xx][yy] stp[f.first][f.second] 1;}}}
}int main()
{memset(vis, 0, sizeof(vis));memset(stp, -1, sizeof(stp));cin n m x y;stp[x][y] 0;vis[x][y] true;q.push(make_pair(x, y));bfs(x, y);for (int i 1; i n; i){for (int j 1; j m; j){printf(%-5d, stp[i][j]);}putchar(\n);}return 0;
}
