题目描述

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;
}