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
输入数据 1
3 4 A... ##.# ...B输出数据 1
5样例 2
输入数据 2
3 5 A.K## ##### ....B输出数据 2
6样例解释
样例 1 中，AC鸭不需要按钮，直接绕过墙走到出口，最少需要 5 步。
样例 2 中，AC鸭先从A走到按钮K，之后墙全部打开，就可以向下穿过墙，再走到出口B。
数据规模
| 子任务 | 占比 | 特殊性质 |
|---|---|---|
| 1 | 20% | 1≤n,m≤20，没有按钮K |
| 2 | 30% | 1≤n,m≤1000，没有按钮K |
| 3 | 50% | 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(){ cin>>n>>m; for(int i = 1;i <= n;i++){ cin>>s[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); cout<<min(a[0][xx][yy],a[1][xx][yy]); return 0; }