AC鸭的迷宫按钮

题目描述AC鸭来到一个迷宫里迷宫有 n 行 m 列。迷宫中有五种字符A表示 AC鸭一开始的位置。B表示出口的位置。.表示可以经过的空地。#表示一开始不能经过的墙。K表示按钮。AC鸭每一步可以向上、下、左、右四个方向移动一格不能走出迷宫。如果 AC鸭还没有到达过按钮K那么他不能走到墙#上。一旦 AC鸭到达任意一个按钮K之后所有墙#都会打开AC鸭就可以把墙当成普通空地经过。请你求出 AC鸭从A走到B至少需要多少步。如果无法到达输出-1。输入格式第一行两个整数 n,m表示迷宫的行数和列数。接下来 n 行每行一个长度为 m 的字符串表示迷宫。输出格式输出一个整数表示从A到B的最少步数。如果无法到达输出-1。样例 1输入数据 13 4 A... ##.# ...B输出数据 15样例 2输入数据 23 5 A.K## ##### ....B输出数据 26样例解释样例 1 中AC鸭不需要按钮直接绕过墙走到出口最少需要 5 步。样例 2 中AC鸭先从A走到按钮K之后墙全部打开就可以向下穿过墙再走到出口B。数据规模子任务占比特殊性质120%1≤n,m≤20没有按钮K230%1≤n,m≤1000没有按钮K350%1≤n,m≤2000保证迷宫中恰好有一个A和一个B。题解解题思路分析该代码解决的是一个网格地图中的路径搜索问题主要目标是找到从起点到终点的最短路径同时考虑特定条件下的路径优化。以下是代码的核心思路解析网格地图处理输入一个n×m的网格地图每个格子可能包含不同字符如A、B、K、#等。地图中的障碍物用#表示不可通行。起点标记为A终点标记为B。数据结构设计使用三维数组a[2][2010][2010]存储两个不同状态下的最短路径距离a[0][i][j]表示未触发特殊条件时从起点到(i,j)的最短距离。a[1][i][j]表示触发特殊条件后从起点到(i,j)的最短距离。使用三维数组b[2][2010][2010]标记障碍物或已访问状态。深度优先搜索DFS从起点A开始进行DFS遍历记录到达每个格子的步数。在DFS过程中如果遇到字符K可能是传送点或关键点更新终点B在状态1下的最短距离计算从当前点(x,y)到终点(xx,yy)的曼哈顿距离即|x-xx| |y-yy|。将该距离与当前步数相加作为状态1下终点的可能最短距离。每次移动上、下、左、右步数增加1递归搜索直到边界或障碍物。结果输出最终比较两种状态下到达终点B的最短距离a[0][xx][yy]和a[1][xx][yy]取较小值作为答案。关键点说明曼哈顿距离的应用在遇到K时直接计算到终点的曼哈顿距离可能用于模拟传送或快速移动的机制。双状态设计通过区分是否触发特殊条件如遇到K分别记录路径距离确保最优解覆盖两种场景。障碍物处理通过b[0][i][j]标记障碍物DFS中遇到障碍物或越界时直接返回。改进建议该代码使用DFS可能导致重复计算或栈溢出对于大规模网格建议改用BFS广度优先搜索更高效。曼哈顿距离的假设可能需要根据题目具体要求验证例如是否允许对角线移动。解决代码#include bits/stdc.h using namespace std; int n,m; int xx,yy,q1,q2; bool b[2][2010][2010] {0}; int a[2][2010][2010] {0}; string s[2010]; void DFS(int f,int x,int y,int w){ if(a[f][x][y] w || x n || y m || x 1 || y 1 || b[f][x][y] 1){ return ; } a[f][x][y] w; if(s[x][y] K){ a[1][xx][yy] w abs(xx - x) abs(yy - y); } w; DFS(f,x 1,y,w); DFS(f,x,y 1,w); DFS(f,x - 1,y,w); DFS(f,x,y - 1,w); } int main(){ cinnm; for(int i 1;i n;i){ cins[i]; s[i] s[i]; for(int j 1;j s[i].size();j){ a[0][i][j] 1000000000; a[1][i][j] 1000000000; if(s[i][j] #){ b[0][i][j] 1; } if(s[i][j] B){ xx i,yy j; } if(s[i][j] A){ q1 i,q2 j; } } } DFS(0,q1,q2,0); coutmin(a[0][xx][yy],a[1][xx][yy]); return 0; }