1 条题解
-
0
#include<bits/stdc++.h> using namespace std; // [1] 12种合法移动方向:前8个是马走日,后4个是象走田 int dx[] = {1, 1, -1, -1, 2, 2, -2, -2, 2, 2, -2, -2}; int dy[] = {2, -2, 2, -2, 1, -1, 1, -1, 2, -2, 2, -2}; // [2] dist[x][y]:从(x,y)到(1,1)的最少步数 int dist[105][105]; // 棋盘大小为100×100,坐标范围1~100 const int MAX_BOARD = 100; // [3] BFS预处理:从终点(1,1)出发,计算所有点的最少步数 void bfs_preprocess() { // 初始化距离数组为-1,表示该点未被访问 memset(dist, -1, sizeof(dist)); // 队列存储待遍历的坐标 queue<pair<int, int>> q; // 起点(1,1)的步数为0,入队启动BFS dist[1][1] = 0; q.push({1, 1}); // 标准BFS循环,层级遍历所有可达点 while(!q.empty()) { // 取出队首的当前坐标 auto cur = q.front(); q.pop(); int x = cur.first; int y = cur.second; // 遍历12种移动方向 for(int i = 0; i < 12; i++) { // 计算移动后的新坐标 int nx = x + dx[i]; int ny = y + dy[i]; // 合法性检查:坐标在棋盘内,且未被访问过 if(nx >= 1 && nx <= MAX_BOARD && ny >= 1 && ny <= MAX_BOARD && dist[nx][ny] == -1) { // 步数+1,标记已访问,新坐标入队 dist[nx][ny] = dist[x][y] + 1; q.push({nx, ny}); } } } } int main() { // [4] 预处理整个棋盘的最少步数,仅需执行一次 bfs_preprocess(); // [5] 读取两个马的坐标 int x1, y1, x2, y2; cin >> x1 >> y1; cin >> x2 >> y2; // [6] 直接查表输出两个坐标的最少步数 cout << dist[x1][y1] << endl; cout << dist[x2][y2] << endl; return 0; }
- 1
信息
- ID
- 1308
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 1
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者