当前位置：首页 > news >正文

UVa 439 Knight Moves

news 2026/6/9 13:33:30

题目描述

题目要求计算国际象棋棋盘上骑士从一个方格移动到另一个方格所需的最少步数。骑士的移动方式为“日”字形（水平移动222格、垂直移动111格，或水平移动111格、垂直移动222格）。

输入格式

输入包含多行，每行两个字符串，表示起点方格和终点方格。方格由一个小写字母（a∼h\texttt{a} \sim \texttt{h}a∼h，表示列）和一个数字（1∼8\texttt{1} \sim \texttt{8}1∼8，表示行）组成。输入以文件结束符（EOF\texttt{EOF}EOF）终止。

输出格式

对于每个测试用例，输出一行：

To get from xx to yy takes n knight moves.

样例

输入

e2 e4 a1 b2 b2 c3 a1 h8 a1 h7 h8 a1 b1 c3 f6 f6

输出

To get from e2 to e4 takes 2 knight moves. To get from a1 to b2 takes 4 knight moves. To get from b2 to c3 takes 2 knight moves. To get from a1 to h8 takes 6 knight moves. To get from a1 to h7 takes 5 knight moves. To get from h8 to a1 takes 6 knight moves. To get from b1 to c3 takes 1 knight moves. To get from f6 to f6 takes 0 knight moves.

题目分析

本题的核心是在8×88 \times 88×8的棋盘上，使用广度优先搜索（BFS\texttt{BFS}BFS）计算从起点到终点的最短路径长度。由于棋盘规模固定且较小，BFS\texttt{BFS}BFS可以高效地找到最少步数。

坐标转换

将棋盘坐标转换为000到777的整数索引：

行：字符1∼8\texttt{1} \sim \texttt{8}1∼8转换为0∼70 \sim 70∼7（或777到000，不影响结果）。
列：字符a∼h\texttt{a} \sim \texttt{h}a∼h转换为0∼70 \sim 70∼7。

骑士移动

骑士的888个可能移动方向为：
(±2,±1),(±1,±2) (\pm 2, \pm 1), (\pm 1, \pm 2)(±2,±1),(±1,±2)

广度优先搜索

从起点开始，使用队列进行BFS\texttt{BFS}BFS：

初始化距离数组dist[8][8]\textit{dist}[8][8]dist[8][8]为−1-1−1，dist[startRow][startCol]=0\textit{dist}[\textit{startRow}][\textit{startCol}] = 0dist[startRow][startCol]=0。
将起点入队。
当队列非空时，取出队首节点，遍历888个邻接位置，若未访问且不越界，则设置距离为当前距离+1+1+1，并加入队列。
搜索结束后，dist[endRow][endCol]\textit{dist}[\textit{endRow}][\textit{endCol}]dist[endRow][endCol]即为最少步数。

边界情况

起点等于终点时，步数为000。

复杂度分析

BFS\texttt{BFS}BFS遍历整个棋盘最多646464个节点，每条边检查888个方向，时间复杂度O(64×8)=O(1)O(64 \times 8) = O(1)O(64×8)=O(1)。每组测试用例独立运行，完全可接受。

代码实现

// Knight Moves// UVa ID: 439// Verdict: Accepted// Submission Date: 2016-07-13// UVa Run Time: 0.010s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;structstate{introw,column;};intoffset[8][2]={{-2,-1},{-2,1},{-1,-2},{-1,2},{2,1},{2,-1},{1,2},{1,-2}};intmain(intargc,char*argv[]){ios::sync_with_stdio(false);string from,to;while(cin>>from>>to){intstart_row=from.back()-'1',start_column=from.front()-'a';intend_row=to.back()-'1',end_column=to.front()-'a';intvisited[8][8]={},moves[8][8]={};queue<state>unvisited;unvisited.push((state){start_row,start_column});visited[start_row][start_column]=1;moves[start_row][start_column]=0;while(!unvisited.empty()){state current=unvisited.front();unvisited.pop();for(inti=0;i<8;i++){intnext_row=current.row+offset[i][0],next_column=current.column+offset[i][1];if(next_row>=0&&next_row<8&&next_column>=0&&next_column<8&&visited[next_row][next_column]==false){moves[next_row][next_column]=moves[current.row][current.column]+1;unvisited.push((state){next_row,next_column});visited[next_row][next_column]=1;}}}cout<<"To get from "<<from<<" to "<<to<<" takes "<<moves[end_row][end_column]<<" knight moves."<<endl;}return0;}