题解
【基础】骑士巡游
1 条题解
-
0
#include <bits/stdc++.h> using namespace std; int n,m; // 棋盘的行数和列数 int sx, sy; // 初始位置坐标 int ex, ey; // 目标位置坐标 int a[10][10]; // 棋盘数组,标记访问状态 int fx[8]={-2, -1, 1, 2, 2, 1, -1, -2}; // 骑士的8个可能移动方向的x偏移量 int fy[8]={1, 2, 2, 1, -1, -2, -2, -1}; // 骑士的8个可能移动方向的y偏移量 int ans = INT_MAX; // 记录最短路径长度,初始化为最大整数值 /* 算法思路: 1) 使用fx和fy数组定义骑士的8个可能移动方向 2) 使用深度优先搜索遍历所有可能路径 3) 记录到达每个位置的最小步数 4) 通过回溯确保每个位置只被访问一次 */ // 深度优先搜索函数 // x, y: 当前位置坐标 // cnt: 已走步数 void dfs(int x, int y, int cnt){ if(x == ex && y == ey){ // 到达目标位置 ans = min(ans, cnt); // 更新最短路径长度 return; } a[x][y] = 1; // 标记当前位置为已访问 // 尝试8个可能的移动方向 for(int i=0;i<8;i++){ int tx = x + fx[i]; // 计算新位置的x坐标 int ty = y + fy[i]; // 计算新位置的y坐标 // 检查新位置是否合法且未被访问过 if(tx >= 1 && tx <= n && ty >= 1 && ty <= m && a[tx][ty] == 0){ dfs(tx, ty, cnt+1); // 递归搜索 a[tx][ty] = 0; // 回溯:撤销标记,允许其他路径访问 } } } int main() { cin >> n >> m >> sx >> sy >> ex >> ey; // 输入棋盘大小和起止位置 dfs(sx, sy, 0); // 从初始位置开始搜索,初始步数为0 cout << ans; // 输出最短路径长度 return 0; }
- 1