不正经题解|仙岛求药

迷宫模板题，推荐用BFS，DFS不能保证最短路径。
【AC代码（有注释）】

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
 
// 定义节点结构体，存储坐标和步数 
struct Node{
    int x,y,step;  // x,y为坐标，step为到达该点的步数
};
 
// BFS搜索函数，寻找从起点到终点的最短路径 
void bfs(int sx,int sy,int ex,int ey,int m,int n,char grid[2005][2005]){
    queue<Node> q;  // BFS队列
    // 创建访问标记数组，防止重复访问
    vector<vector<bool>> vis(m+5,vector<bool>(n+5));
    
    // 将起点加入队列，并标记为已访问
    q.push({sx,sy,0});
    vis[sx][sy]=true;
    
    // 四个方向的偏移量数组：右、下、左、上
    int dx[5]={0,0,1,0,-1},dy[5]={0,1,0,-1,0};
    
    while(!q.empty()){  // 当队列不为空时继续搜索
        Node now=q.front();  // 取出队首元素
        q.pop();
        
        // 如果找到仙药，输出步数并返回 
        if(now.x==ex&&now.y==ey){
            cout<<now.step;
            return;
        }
        
        // 遍历四个方向
        for(int i=1;i<5;++i){
            // 计算新位置 
            int nx=now.x+dx[i],ny=now.y+dy[i];
            
            // 检查新位置是否合法：在边界内、不是怪物、未被访问过
            if(nx>=1&&nx<=m&&ny>=1&&ny<=n&&grid[nx][ny]!='#'&&!vis[nx][ny]){
                // 将新位置加入队列，步数加1，并标记为已访问 
                q.push({nx,ny,now.step+1});
                vis[nx][ny]=true;
            }
        }
    }
    // 如果无法找到仙药，输出-1
    cout<<-1;
}
 
int main(){
    int m=0,n=0;  // 地图的行数和列数
    cin>>m>>n;
    char grid[2005][2005];  // 存储地图信息的二维数组 
    
    int sx=0,sy=0,ex=0,ey=0;  // 起点和终点坐标
    
    // 读入地图，并记录起点('@')和仙药('*')的位置
    for(int i=1;i<=m;++i){
        for(int j=1;j<=n;++j){
            cin>>grid[i][j];
            if(grid[i][j]=='@'){  // 找到起点
                sx=i;
                sy=j;
            }
            if(grid[i][j]=='*'){  // 找到仙药
                ex=i;
                ey=j;
            }
        }
    }
    
    // 调用BFS函数寻找最短路径
    bfs(sx,sy,ex,ey,m,n,grid);
    return 0;
}

时间复杂度：
O(nm)