UVa 439 Knight Moves

题目描述题目要求计算国际象棋棋盘上骑士从一个方格移动到另一个方格所需的最少步数。骑士的移动方式为“日”字形水平移动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−1dist[startRow][startCol]0\textit{dist}[\textit{startRow}][\textit{startCol}] 0dist[startRow][startCol]0。将起点入队。当队列非空时取出队首节点遍历888个邻接位置若未访问且不越界则设置距离为当前距离111并加入队列。搜索结束后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//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;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(cinfromto){intstart_rowfrom.back()-1,start_columnfrom.front()-a;intend_rowto.back()-1,end_columnto.front()-a;intvisited[8][8]{},moves[8][8]{};queuestateunvisited;unvisited.push((state){start_row,start_column});visited[start_row][start_column]1;moves[start_row][start_column]0;while(!unvisited.empty()){state currentunvisited.front();unvisited.pop();for(inti0;i8;i){intnext_rowcurrent.rowoffset[i][0],next_columncurrent.columnoffset[i][1];if(next_row0next_row8next_column0next_column8visited[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;}}}coutTo get from from to to takes moves[end_row][end_column] knight moves.endl;}return0;}