马的遍历

链接

这题可以用递推的方式解决

我们设置一个二维数组,并初始化为-1 比如马一步可以眺到(2,2)而无法跳到(4,3),但从(2,2)可以跳到(4,3),那么(4,3)就是两步, 从(4,3)开始眺,如果跳到非-1的位置时,那个位置就是三步,依次类推

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
int board[401][401];
int dx[8] = { 1,2,2,1,-1,-2,-2,-1 };
int dy[8] = { 2,1,-1,-2,-2,-1,1,2 };

struct node {
	int x;
	int y;
};
void f(node horse, int n, int m) {
	memset(board, -1, sizeof(board));
	queue<node>check;
	board[horse.x][horse.y] = 0;
	check.push(horse);
	while (!check.empty()) {
		node h = check.front();
		check.pop();
		for (int i = 0;i < 8;i++) {
			for (int j = 0;j < 8;j++) {
				int nx = dx[i] + h.x, ny = dy[i] + h.y;
				if (0 < nx && nx <= n && 0 < ny && ny <= m && board[nx][ny] == -1) {
					board[nx][ny] = board[h.x][h.y] + 1;
					check.push({ nx,ny });
				}
			}
		}
	}
}
int main() {
	int n, m, x, y;
	cin >> n >> m >> x >> y;
	node horse = { x,y };
	f(horse, n, m);
	for (int i = 1;i <= n;i++) {
		for (int j = 1;j <= m;j++) {
			cout << board[i][j] << " ";
		}
		cout << endl;
	}
}

时间复杂度:O(n * m)

空间复杂度:O(n * m)