P1735 字母迷宫【洛谷算法习题】

P1735 字母迷宫网页链接P1735 字母迷宫题目描述打败了 DIABLOMini 进入了迷宫。这是个奇怪的迷宫迷宫的每一个地点要么有一个用来传送的门要么是障碍。Mini 现在站在迷宫的原点处但是眼看远在( N , N ) (N,N)(N,N)的公主就要被转移Mini 心情焦急万分为了能最快地到达公主处救出公主Mini 希望能走一条最快的路径。注意Mini 可以把迷宫的( 1 , 1 ) (1,1)(1,1)或( 1 , N ) (1,N)(1,N)或( N , 1 ) (N,1)(N,1)处当作原点。迷宫里某些地点会有门将门激活Mini 就会被传送到某个地点当然魔王 Bill 只创造了三种门所以迷宫里最多有就只有三种门而且在这个迷宫中要到达下一个点必须通过门。。什么逻辑 TUT。。在迷宫中可能会遇到的三种门分别如下时空之门Mini 可以往上下左右四个方向中的任意一个方向传送一格海洋之门Mini 可以往上下左右四个方向中的任意一个方向传送两格天堂之门Mini 需要停留一步聚气然后可以往左上左下右上右下四个方向中的任意一个方向传送一格。当然使用每一个门都算作一步。当然还有障碍如果有障碍那么这个点没有门且这个点不能被传送到。但是魔王 Bill 有可能创造出了一个完全无法到达( N , N ) (N,N)(N,N)的迷宫所以当从三个原点出发都无法到达( N , N ) (N,N)(N,N)时请输出No answer。注意原点算作一步Mini 一开始站在( 1 , 1 ) (1,1)(1,1)或( 1 , N ) (1,N)(1,N)或( N , 1 ) (N,1)(N,1)的位置然后走一步到原点所以原点算作一步。输入格式第一行一个数N NN表示迷宫的大小N × N N\times NN×N。以下N NN行每行N NN个字符表示迷宫的示意图。字符要么是字母 ABC要么是障碍。A 表示时空之门B 表示海洋之门C 表示天堂之门障碍用∗ *∗表示。输出格式输出为 Mini 从原点处走到公主处的最快路径长度。无解输出No answer。输入输出样例 #1输入 #13 A*C *AC ACA输出 #1No answer输入输出样例 #2输入 #23 AAA CAA AAA输出 #23说明/提示对于100 % 100\%100%的数据0 ≤ N ≤ 1200 0\le N\le 12000≤N≤1200。解题思路本题是迷宫最短路径搜索问题采用广度优先搜索BFS求解。迷宫中的每个格子可能有三种不同的门A、B、C或障碍*每种门对应不同的移动规则。需要从三个可能的原点(1,1)、(1,N)、(N,1)出发找到到达(N,N)的最短步数若无法到达则输出No answer。1. 问题等价转化将迷宫视为一个N × N N \times NN×N的网格图每个非障碍格子为可到达的节点。移动规则由当前格子的门类型决定A时空之门向上下左右四个方向移动 1 格消耗 1 步。B海洋之门向上下左右四个方向移动 2 格消耗 1 步。C天堂之门需要先原地停留 1 步聚气消耗 1 步然后向四个斜方向左上、左下、右上、右下移动 1 格再消耗 1 步。因此使用 C 门完整移动一次共需 2 步。起点有三个可选(1,1)、(1,N)、(N,1)题目规定“原点算作一步”因此从起点出发时步数初始为 1。目标到达(N,N)求最小步数。2. 算法实现BFS使用队列进行 BFS队列元素包含坐标(x, y)、当前步数step以及一个标志flag用于记录在 C 门处是否已经聚气。初始化检查三个起点是否为障碍若不为障碍则入队step 1flag 0。使用二维布尔数组V[x][y]标记已访问的格子防止重复入队。BFS 扩展取出队首状态若坐标为(N,N)直接输出step并结束。根据当前格子的字符A枚举四个方向移动 1 格。若新位置在界内、非障碍且未访问标记访问并入队step 1flag 0。B枚举四个方向移动 2 格。同样检查合法性入队step 1flag 0。C若flag 0原地停留步数加 1flag 1重新入队表示聚气。若flag 1枚举四个斜方向移动 1 格。检查合法性入队step 1flag 0。终止条件若队列为空仍未到达终点输出No answer。注意若终点本身是障碍直接输出No answer。3. 复杂度分析时间复杂度每个格子最多被访问一次代码中使用二维V数组每次扩展最多枚举 4 个方向因此总时间复杂度为O ( N 2 ) O(N^2)O(N2)。N ≤ 1200 N \le 1200N≤1200N 2 ≈ 1.44 × 10 6 N^2 \approx 1.44 \times 10^6N2≈1.44×106完全可行。空间复杂度需要存储迷宫字符矩阵和访问标记数组均为O ( N 2 ) O(N^2)O(N2)队列最多存储O ( N 2 ) O(N^2)O(N2)个状态。4. 总结利用 BFS 的层次遍历特性天然求解最短路径。关键在于正确处理三种门的移动规则尤其是 C 门需要两步聚气移动以及状态标志flag的维护。起点有三个初始步数为 1需要注意起点的合法性检查。代码简要说明全局变量A[1205][1205]存储迷宫字符V[1205][1205]标记访问方向数组D1四方向和D3斜方向。结构体ND包含坐标x, y、步数step和聚气标志flag。BFS 函数将三个合法起点入队step 1。循环取出队首若到达(n,n)则输出步数并返回。根据当前字符执行对应的移动逻辑更新步数和标志将合法新状态入队。主函数读入N NN和迷宫若终点为障碍则直接输出No answer否则调用 BFS若未找到路径则输出No answer。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;ll n;charA[1205][1205];boolV[1205][1205];ll D1[2][5]{{1,0,-1,0},{0,1,0,-1}};ll D3[2][5]{{1,1,-1,-1},{-1,1,1,-1}};structND{ll x,y,step;boolflag;};boolF;voidBFS(){queueNDq;if(A[1][1]!*)q.push(ND{1,1,1,0});if(A[1][n]!*)q.push(ND{1,n,1,0});if(A[n][1]!*)q.push(ND{n,1,1,0});while(!q.empty()){ND nowq.front();q.pop();if(now.xnnow.yn){F1;coutnow.step;return;}if(A[now.x][now.y]A){for(ll i0;i4;i){ll xxnow.xD1[0][i],yynow.yD1[1][i];if(xx1xxnyy1yyn!V[xx][yy]A[xx][yy]!*){V[xx][yy]1;q.push(ND{xx,yy,now.step1,0});}}}elseif(A[now.x][now.y]B){for(ll i0;i4;i){ll xxnow.x2*D1[0][i],yynow.y2*D1[1][i];if(xx1xxnyy1yyn!V[xx][yy]A[xx][yy]!*){V[xx][yy]1;q.push(ND{xx,yy,now.step1,0});}}}elseif(A[now.x][now.y]C){if(now.flag0){q.push(ND{now.x,now.y,now.step1,1});continue;}for(ll i0;i4;i){ll xxnow.xD3[0][i],yynow.yD3[1][i];if(xx1xxnyy1yyn!V[xx][yy]A[xx][yy]!*){V[xx][yy]1;q.push(ND{xx,yy,now.step1,0});}}}}}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cinn;for(ll i1;in;i)for(ll j1;jn;j)cinA[i][j];if(A[n][n]*){coutNo answer;return0;}BFS();if(F0){coutNo answer;return0;}return0;}