企业官网建设流程全解析

题目描述

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。

数据规模

保证迷宫中恰好有一个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; }