Horse traversal
Title Description
There is a\(n \times m\) of the chessboard, at some point\((x, y)\) There is a knight on the board, and you are asked to calculate the minimum number of moves it will take for the knight to reach any point on the board.
input format
The input has only one line of four integers, which are\(n, m, x, y\)。
output format
an\(n \times m\) is a matrix representing the minimum number of steps a horse has to take to reach a certain point (or output if it can't).\(-1\)）。
Sample #1
Sample Input #1
3 3 1 1
Sample Output #1
0 3 2
3 -1 1
2 1 4
draw attention to sth.
Data size and conventions
For the full range of test points, ensure that\(1 \leq x \leq n \leq 400\)，\(1 \leq y \leq m \leq 400\)。
Problem analysis
Regular bfs questions, eight directions per entry, and mark the number of layers at the time of entry, which is the number of steps the horse has skipped, and the earlier it skips to, the fewer steps it spends
#include <iostream>
#include <iomanip>;
#include<iostream> #include <iomanip> #include<cstring>
#include<queue> #include<iomanip> #include<cstring>
using namespace std.
int n, m, x, y; bool flag[450
bool flag[450][450]; //determine whether to walk across
int step[450][450] ; //record the number of steps
int dir[8][8] = { {1,2},{1,-2},{-1,2},{-1,-2},{2,1},{2,-1},{-2,1},{-2,-1} }; // eight directions
queue<pair<int, int> >que; //These two consecutive >> are better off with a space, some systems report errors
void bfs(int x, int y) {
step[x][y] = 0;
flag[x][y] = true;
(make_pair(x, y)).
while (! ()) {
pair<int, int>t = ().
();
//flag[][] = true; //wrote the flag here at the beginning and didn't notice that the horse might jump back, so it should be flagged when it enters the queue again
for (int i = 0; i < 8; i++) {
int nx = + dir[i][0], ny = + dir[i][1];
if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && !flag[nx][ny]) {
(make_pair(nx, ny)).
flag[nx][ny] = true; //flag
step[nx][ny] = step[][] + 1; //record the number of steps
}
}
}
}
int main() {
cin >> n >> m >> x >> y.
memset(flag, false, sizeof(flag)); memset(step, -1, sizeof(flag)); memset(step, -1, sizeof(y))
memset(step, -1, sizeof(step)); //initialized to -1
bfs(x, y);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cout << left << setw(5) << step[i][j]; // note output formatting
}
cout << endl.
}
return 0;
}