2510: 【普及/提高-】【P1443】马的遍历

内存限制：128 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：19 解决：7

题目描述

有一个 lns="http://www.w3.org/1998/Math/MathML">�×� 的棋盘，在某个点 lns="http://www.w3.org/1998/Math/MathML">(�,�) 上有一个马，要求你计算出马到达棋盘上任意一个点最少要走几步。

输入

输入只有一行四个整数，分别为 lns="http://www.w3.org/1998/Math/MathML">�,�,�,�。

输出

一个 lns="http://www.w3.org/1998/Math/MathML">�×� 的矩阵，代表马到达某个点最少要走几步（不能到达则输出 lns="http://www.w3.org/1998/Math/MathML">−1）。

样例输入 复制 

3 3 1 1

样例输出 复制 

0    3    2    
3    -1   1    
2    1    4

提示

数据规模与约定

对于全部的测试点，保证 lns="http://www.w3.org/1998/Math/MathML">1≤�≤�≤400，lns="http://www.w3.org/1998/Math/MathML">1≤�≤�≤400。 


#include<bits/stdc++.h>
using namespace std;
#define maxn 310
struct coord { //一个结构体存储x,y两个坐标
    int x, y;
};
queue<coord> Q;//队列
int ans[maxn][maxn];//记录答案，-1表示未访问
int walk[8][2] = {{2, 1}, {1, 2}, {-1, 2}, {-2, 1},{-2, -1}, {-1, -2}, {1, -2}, {2, -1}};
int main(){
	int n,m,sx,sy;
	memset(ans,-1,sizeof(ans));
	cin>>n>>m>>sx>>sy; 
    coord tmp = {sx, sy};
    Q.push(tmp); // 使起点入队扩展
    ans[sx][sy] = 0;
    while (!Q.empty()) { // 循环直到队列为空
        coord u = Q.front(); // 拿出队首以扩展
        int ux = u.x, uy = u.y;
        Q.pop();
        for (int k = 0; k < 8; k++) {
            int x = ux + walk[k][0], y = uy + walk[k][1];
            int d = ans[ux][uy];
            if (x < 1 || x > n || y < 1 || y > m || ans[x][y] != -1)
                continue; // 若坐标超过地图范围或者该点已被访问过则无需入队
            ans[x][y] = d + 1; // 记录答案，是上一个点多走一步的结果。
            coord tmp = {x, y};
            Q.push(tmp);
       }
    }
    for (int i=1;i<=n;i++,puts(""))
        for (int j=1;j<=m;j++)
            printf("%-5d",ans[i][j]);  //场宽输出 
	return 0;
}


来源/分类

提交提交记录统计露一手!