题目描述在一个2N×2N2N \times 2N2N×2N的棋盘上3≤N≤203 \le N \le 203≤N≤20有一只“动态骑士”。它可以执行三种类型的移动K\texttt{K}K型与常规国际象棋骑士相同即沿水平或垂直方向移动222格再沿垂直方向移动111格共有888个可能的方向。B\texttt{B}B型沿对角线方向移动222格共有444个可能的方向。T\texttt{T}T型沿棋盘的水平中轴或垂直中轴进行镜像反射即坐标(x,y)(x, y)(x,y)变为(2N1−x,y)(2N1-x, y)(2N1−x,y)或(x,2N1−y)(x, 2N1-y)(x,2N1−y)。骑士不能走出棋盘也不能落在障碍物上。此外骑士不能连续两次使用相同类型的移动第一次移动可以任意类型。给定起点和终点求从起点到终点的最少移动次数。如果无法到达则报告无解。输入格式输入包含多组测试用例。每个测试用例的第一行为一个整数NNNN0N 0N0棋盘大小为2N×2N2N \times 2N2N×2N。第二行为起点坐标(xs,ys)(x_s, y_s)(xs​,ys​)第三行为终点坐标(xt,yt)(x_t, y_t)(xt​,yt​)。随后若干行给出障碍物的坐标每行两个整数以0 0结束障碍物描述。输入以单独的N0N 0N0结束。输出格式对于每个测试用例若起点与终点相同输出Result : 0。若终点是障碍物输出Solution doesnt exist。否则输出最少移动次数格式为Result : X其中XXX为步数若不可达则输出Solution doesnt exist。样例输入3 1 1 1 1 2 2 0 0 10 1 1 20 20 20 1 1 20 3 1 3 2 3 3 2 3 1 3 0 0 10 2 1 18 12 2 2 5 6 7 2 8 3 9 4 1 15 7 12 8 13 9 11 11 9 12 4 11 3 9 5 2 7 3 8 6 5 0 0 3 1 1 5 4 2 2 2 4 2 5 3 1 3 2 3 3 3 6 4 2 4 3 4 5 5 1 5 3 5 5 6 1 6 4 6 5 6 6 0 0输出Result : 0 Solution doesnt exist Result : 6 Result : 4题目分析本题要求在带障碍物的棋盘上求最短路径但移动规则比常规骑士复杂且包含三种不同类型的移动并限制不能连续使用同类型。由于移动类型只有三种且每种类型的移动数量有限K\texttt{K}K型888种B\texttt{B}B型444种T\texttt{T}T型222种棋盘最大尺寸为40×4040 \times 4040×40状态总数可控。最短路问题可以用广度优先搜索BFS\texttt{BFS}BFS求解但状态不仅包含坐标(x,y)(x, y)(x,y)还需要记录上一步使用的移动类型因为规则限制了连续相同类型。因此每个位置对应444个状态上一步为无、K\texttt{K}K、B\texttt{B}B、T\texttt{T}T分别标记访问情况。BFS\texttt{BFS}BFS从起点开始每次扩展所有合法移动并确保新移动的类型与上一步不同。当扩展到终点时当前步数即为最少步数。解题思路状态表示与访问标记定义结构体movement包含坐标x、y、当前步数steps以及上一步移动类型lastMoveType000表示起点无上一步111表示K\texttt{K}K222表示B\texttt{B}B333表示T\texttt{T}T。使用三维数组visited[x][y][type]记录是否已访问过该状态其中type对应上一步的类型000到333。若visited[x][y][type]为真则不再入队因为BFS\texttt{BFS}BFS首次访问即最优。移动生成K\texttt{K}K型枚举888个偏移量(Δx,Δy)∈{(−2,−1),(−1,−2),(1,−2),(2,−1),(2,1),(1,2),(−1,2),(−2,1)}(\Delta x, \Delta y) \in \{(-2,-1),(-1,-2),(1,-2),(2,-1),(2,1),(1,2),(-1,2),(-2,1)\}(Δx,Δy)∈{(−2,−1),(−1,−2),(1,−2),(2,−1),(2,1),(1,2),(−1,2),(−2,1)}检查目标坐标是否在棋盘内且非障碍物。B\texttt{B}B型枚举444个偏移量(Δx,Δy)∈{(−2,−2),(2,−2),(2,2),(−2,2)}(\Delta x, \Delta y) \in \{(-2,-2),(2,-2),(2,2),(-2,2)\}(Δx,Δy)∈{(−2,−2),(2,−2),(2,2),(−2,2)}同样检查合法性。T\texttt{T}T型计算镜像坐标(2N1−x,y)(2N1-x, y)(2N1−x,y)和(x,2N1−y)(x, 2N1-y)(x,2N1−y)若目标非障碍物则入队。搜索流程读入NNN若N0N0N0则结束。读入起点、终点并读入障碍物坐标直到0 0。若起点与终点重合输出Result : 0并继续下一组。若终点是障碍物输出Solution doesnt exist并继续。初始化队列将起点状态lastMoveType 0步数为000入队并标记visited[startx][starty][0] 1。执行BFS\texttt{BFS}BFS取出队首状态。若坐标等于终点输出当前步数并标记找到。否则对于三种移动类型若当前上一步类型不等于该类型尝试所有该类型的合法移动若目标状态未访问则入队并标记。若队列空仍未找到输出Solution doesnt exist。边界与剪枝棋盘大小最大404040状态数为40×40×4640040 \times 40 \times 4 640040×40×46400非常小。注意T型移动可能回到自身当xN0.5x N0.5xN0.5时但2N2N2N为偶数镜像坐标不可能与自身重合因为(2N1−x)x(2N1-x) x(2N1−x)x得到xN0.5x N0.5xN0.5不是整数所以不会自环。障碍物只禁止停留不禁止经过移动是跳跃式的不经过中间格。复杂度分析每个状态最多扩展一次状态数为O((2N)2×4)O(N2)O((2N)^2 \times 4) O(N^2)O((2N)2×4)O(N2)N≤20N \le 20N≤20故状态数不超过640064006400。每次扩展尝试最多84214842 1484214种移动总扩展次数O(N2×14)O(N^2 \times 14)O(N2×14)非常小。空间复杂度O(N2)O(N^2)O(N2)。代码实现// A Chess Knight// UVa ID: 633// Verdict: Accepted// Submission Date: 2017-06-02// UVa Run Time: 0.000s//// 版权所有C2017邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;structmovement{intx,y,steps,lastMoveType;};intmain(){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intobstacle[64][64],visited[64][64][4],n;intoffsetK[8][2]{{-2,-1},{-1,-2},{1,-2},{2,-1},{2,1},{1,2},{-1,2},{-2,1}};intoffsetB[4][2]{{-2,-2},{2,-2},{2,2},{-2,2}};while(cinn,n0){n*2;memset(obstacle,0,sizeof(obstacle));memset(visited,0,sizeof(visited));intstartx,starty,endx,endy;cinstartxstartyendxendy;intobstaclex,obstacley;while(cinobstaclexobstacley){if(obstaclex0obstacley0)break;obstacle[obstaclex][obstacley]1;}if(startxendxstartyendy){coutResult : 0\n;continue;}if(obstacle[endx][endy]){coutSolution doesnt exist\n;continue;}queuemovementunvisited;unvisited.push(movement{startx,starty,0,0});boolfoundfalse;while(!unvisited.empty()){movement munvisited.front();unvisited.pop();if(m.xendxm.yendy){coutResult : m.steps\n;foundtrue;break;}if(m.lastMoveType!1!visited[m.x][m.y][1]){for(inti0;i8;i){intnextxm.xoffsetK[i][0],nextym.yoffsetK[i][1];if(nextx1||nextxn||nexty1||nextyn)continue;if(obstacle[nextx][nexty])continue;unvisited.push(movement{nextx,nexty,m.steps1,1});}visited[m.x][m.y][1]1;}if(m.lastMoveType!2!visited[m.x][m.y][2]){for(inti0;i4;i){intnextxm.xoffsetB[i][0],nextym.yoffsetB[i][1];if(nextx1||nextxn||nexty1||nextyn)continue;if(obstacle[nextx][nexty])continue;unvisited.push(movement{nextx,nexty,m.steps1,2});}visited[m.x][m.y][2]1;}if(m.lastMoveType!3!visited[m.x][m.y][3]){intnextxn-m.x1,nextym.y;if(!obstacle[nextx][nexty])unvisited.push(movement{nextx,nexty,m.steps1,3});nextxm.x,nextyn-m.y1;if(!obstacle[nextx][nexty])unvisited.push(movement{nextx,nexty,m.steps1,3});visited[m.x][m.y][3]1;}}if(!found)coutSolution doesnt exist\n;}return0;}总结本题通过引入移动类型和不能连续使用同类型的限制将普通的最短路径问题扩展为带状态的最短路问题。利用BFS\texttt{BFS}BFS在状态空间坐标 上一步类型上进行搜索能够保证首次到达终点时即为最少步数。关键点包括状态设计必须包含上一步移动类型以正确应用限制规则。特殊处理起点与终点重合以及终点为障碍物的情况。移动生成时注意边界检查和障碍物检查。由于棋盘较小状态总数有限BFS\texttt{BFS}BFS效率很高。此解法清晰直观体现了在复杂移动规则下使用BFS\texttt{BFS}BFS求解最短路径的通用思路。