UVa 676 Horse Step Maze

题目描述在一个9×99 \times 99×9的棋盘上计算机鼠标从起点出发以马步类似国际象棋中马的走法但方向固定为四个斜对角方向每次横向111格、纵向111格。搜索规则每次移动前在当前位置放一块石头标记已访问。按方向111、222、333、444的顺序尝试移动方向顺序为(-1,1),(1,1),(1,-1),(-1,-1)。若方向444仍失败则移除石头回溯。若找到路径且步数≤50000\le 50000≤50000输出路径若步数50000 5000050000输出more than 50000 steps若无法到达输出fail。输入格式第一行为整数NNN表示数据集个数。每组数据包含两个坐标格式为(x,y)分别表示起点和终点。各组之间用空行分隔。输出格式对于每组数据若成功且步数≤50000\le 50000≤50000输出路径坐标用逗号和空格分隔若步数超过500005000050000输出more than 50000 steps若无法到达输出fail。每组输出之间用空行分隔。样例输入1 (1,1) (9,9)输出(1,1), (2,2), (1,3), (2,4), (1,5), (2,6), (1,7), (2,8), (1,9), (2,8), (3,9), (4,8), (5,9), (6,8), (7,9), (8,8), (9,9)题目分析本题是带有回溯和步数限制的深度优先搜索DFS\texttt{DFS}DFS。由于棋盘只有9×99 \times 99×9状态有限但搜索可能很长可达500005000050000步因此需要剪枝或限制步数。代码中通过全局moves计数并在递归中检查是否超过500005000050000。另外代码中通过奇偶性判断是否可达dx % 2 ! dy % 2则不可达因为每次移动横向和纵向各变化111所以横纵坐标的奇偶性同时改变因此起点和终点的横纵坐标差必须同奇偶。搜索过程中每次移动后记录路径若到达终点则输出。若方向444仍失败则回溯并移除石头visited[x][y] 0。解题思路读入起点和终点坐标。若起点等于终点直接输出起点。若abs(ex-sx) % 2 ! abs(ey-sy) % 2则不可达输出fail。初始化visited数组为000将起点放入路径并标记为已访问。执行DFS\texttt{DFS}DFS若当前步数moves-1超过500005000050000返回。若当前坐标等于终点输出路径并设置done1返回。标记当前位置已访问。按顺序尝试四个方向若新坐标在棋盘内且未访问则记录路径递归。若递归返回且未完成则记录回溯位置即回到当前位置并继续尝试。若所有方向尝试完清除当前位置的石头visited[x][y]0。若搜索完成但done仍为000输出more than 50000 steps。注意路径输出时每次移动和回溯都会记录坐标因此路径中包含回溯点。复杂度分析棋盘只有818181个格子但搜索可能深度很大500005000050000最坏情况下会遍历大量路径但由于步数限制和奇偶性剪枝实际运行很快。时间复杂度O(states)O(\text{states})O(states)状态数为818181但路径长度可达500005000050000因此输出长度可能很大。代码实现// Horse Step Maze// UVa ID: 676// Verdict: Accepted// Submission Date: 2018-12-27// UVa Run Time: 0.010s//// 版权所有C2018邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intoffset[4][2]{{-1,1},{1,1},{1,-1},{-1,-1}};intvisited[10][10],sx,sy,ex,ey;intpathx[50010],pathy[50010],moves,done;voiddfs(intx,inty){if(done)return;if(moves-150000)return;if(xexyey){for(inti0;imoves;i){if(i)cout, ;cout(pathx[i],pathy[i]);}cout\n;done1;return;}visited[x][y]1;for(intk0;k4;k){intnextxxoffset[k][0],nextyyoffset[k][1];if(nextx1||nextx9||nexty1||nexty9)continue;if(visited[nextx][nexty])continue;pathx[moves]nextx,pathy[moves]nexty,moves;dfs(nextx,nexty);if(done)return;pathx[moves]x,pathy[moves]y,moves;}visited[x][y]0;}intmain(){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);charignore;intcases;cincases;for(intcs1;cscases;cs){if(cs1)cout\n;cinignoresxignoresyignore;cinignoreexignoreeyignore;if(sxexsyey){cout(sx,sy);cout\n;continue;}intdxabs(ex-sx),dyabs(ey-sy);dx%2,dy%2;if(dx!dy){coutfail\n;continue;}movesdone0;memset(visited,0,sizeof(visited));pathx[moves]sx,pathy[moves]sy;moves;dfs(sx,sy);if(!done)coutmore than 50000 steps\n;}return0;}总结本题通过深度优先搜索模拟鼠标在棋盘上按固定顺序探索路径并加入步数限制和奇偶性剪枝。关键点包括正确实现四个方向的有序尝试和回溯。路径记录包含移动和回溯点。利用奇偶性快速判断不可达情况。步数超过500005000050000时提前终止。该解法是经典迷宫搜索的变体适合作为回溯法和剪枝的练习。