题目描述

1
2
3
4
5
6
7
有一个n×m 的棋盘,在某个点(x,y) 上有一个马,要求你计算出马到达棋盘上任意一个点最少要走几步。

输入格式
输入只有一行四个整数,分别为n,m,x,y。

输出格式
一个n×m 的矩阵,代表马到达某个点最少要走几步(左对齐,宽5格,不能到达则输出−1)。

题解

点击查看
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
//————————————————————————————————法一:数组模拟queue----------------------------------
#include <iostream>
#include <cstring>
#include <iomanip>

using namespace std;

const int N = 410;

typedef pair<int, int> PII;

int d[N][N];

PII q[N * N];

int n, m, a, b;

void bfs(int a, int b){
int hh = 0, tt = 0;
q[0] = {a, b};

memset(d, -1, sizeof d);

d[a][b] = 0;

int dx[]{-2, -1, -2, -1, 2, 1, 2, 1};
int dy[]{-1, -2, 1, 2, -1, -2, 1, 2};//向量坐标

while(hh <= tt){
auto t = q[hh++];//取出队头
//向上下左右扩展
for(int i = 0; i < 8; ++i){
int x = t.first + dx[i];
int y = t.second + dy[i];

if(x >= 1 && x <= n && y >= 1 && y <= m && d[x][y] == -1){
d[x][y] = d[t.first][t.second] + 1;
q[ ++ tt] = {x, y};
}
}
}
}

int main(){
ios::sync_with_stdio(false);
cin.tie(0);

cin >> n >> m >> a >> b;

bfs(a, b);

for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cout << setiosflags(ios::left) << setw(5) << d[i][j];
}//设置左对齐,宽度为5
cout << endl;
}

return 0;
}
//————————————————————————————————————法二:STL————————————————————————————————
#include <iostream>
#include <cstring>
#include <queue>
#include <iomanip>

using namespace std;

typedef pair<int, int> PII;

const int N = 410;

int d[N][N];

queue<PII> q;

int n, m, a, b;

void bfs(int a, int b){
q.push({a, b});

memset(d, -1, sizeof d);
d[a][b] = 0;

int dx[]{2, 1, -2, -1, 2, 1, -2, -1};
int dy[]{-1, -2, -1, -2, 1, 2, 1, 2};
while(!q.empty()){
auto t = q.front();
q.pop();
for(int i = 0; i < 8; ++i){
int x = t.first + dx[i];
int y = t.second + dy[i];

if(x >= 1 && y >= 1 && x <= n && y <= m && d[x][y] == -1){
d[x][y] = d[t.first][t.second] + 1;
q.push({x, y});
}
}
}
}

int main(){
ios::sync_with_stdio(false);
cin.tie(0);

cin >> n >> m >> a >> b;

bfs(a, b);

for(int i = 1; i <= n; ++i){
for(int j = 1; j <= m; ++j){
cout << setiosflags(ios::left) << setw(5) << d[i][j];
}
cout << endl;
}

return 0;
}