AtCoder Beginner Contest竞赛题解 | 洛谷 AT_abc436_d Teleport Maze

​欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！

专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。

适合人群：

• 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
• 希望系统学习C++/Python编程的初学者
• 想要提升算法与编程能力的编程爱好者

附上汇总帖：AtCoder Beginner Contest竞赛题解 | 汇总

【题目来源】

洛谷：[AT_abc436_d ABC436D] Teleport Maze - 洛谷

【题目描述】

There is a maze consisting of a grid with $ H $ rows and $ W $ columns. Let $ (i,j) $ denote the cell at the $ i $ -th row from the top and $ j $ -th column from the left. The type of cell $ (i,j) $ is given as a character $ S_{i,j} $ , where each character has the following meaning:

• .: Empty cell
• #: Obstacle cell
• Lowercase English letter (a-z): Warp cell

In the maze, you can perform the following two types of actions any number of times in any order:

• Walk: Move from the current cell to a cell that is one cell away in one of the four directions (up, down, left, right). However, you cannot move to an obstacle cell or outside the grid.
• Warp: When you are at a warp cell, move to any warp cell with the same character written on it.

Determine whether it is possible to move from cell $ (1,1) $ to cell $ (H,W) $ , and if possible, find the minimum total number of actions required.

【输入】

The input is given from Standard Input in the following format:

$ H $ $ W $ $ S_{1,1}S_{1,2}\dots S_{1,W} $ $ \vdots $ $ S_{H,1}S_{H,2}\dots S_{H,W} $

【输出】

If it is possible to move from cell $ (1,1) $ to cell $ (H,W) $ , print the minimum total number of actions required; otherwise, print-1.

【输入样例】

3 4 ..a. #### ba#b

【输出样例】

5

【算法标签】

《洛谷 AT_abc436_d Teleport Maze》 #广度优先搜索BFS#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintN=1005;// 最大网格大小typedefpair<int,int>PII;// 坐标对inth,w;// 网格高度和宽度chara[N][N];// 网格内容intdist[N][N];// 从起点到每个点的最短距离boolvis[N][N];// 访问标记（未使用）intdx[4]={-1,1,0,0};// 上下左右方向intdy[4]={0,0,-1,1};vector<PII>ve[30];// 存储每种小写字母的位置boolst[30];// 标记每种字母是否已使用过传送功能/** * BFS求从(1,1)到(h,w)的最短路径 * 支持普通移动和特殊传送 */voidbfs(){queue<PII>q;q.push({1,1});// 起点dist[1][1]=0;// 起点距离为0while(!q.empty()){intx=q.front().first,y=q.front().second;q.pop();// 如果当前格是小写字母，且该字母的传送功能未使用过if(islower(a[x][y])&&st[a[x][y]-'a']==false){// 遍历该字母对应的所有传送点for(auto[x2,y2]:ve[a[x][y]-'a']){// 如果目标点未访问过if(dist[x2][y2]==-1){// 距离为当前位置距离+1dist[x2][y2]=dist[x][y]+1;// 加入队列q.push({x2,y2});}}// 标记该字母的传送功能已使用st[a[x][y]-'a']=true;}// 四个方向普通移动for(inti=0;i<4;i++){intnx=x+dx[i],ny=y+dy[i];// 边界检查if(nx<1||nx>h||ny<1||ny>w)continue;// 障碍物检查if(a[nx][ny]=='#')continue;// 已访问检查if(dist[nx][ny]!=-1)continue;// 入队并更新距离q.push({nx,ny});dist[nx][ny]=dist[x][y]+1;}}}intmain(){// 输入网格大小cin>>h>>w;// 初始化距离为-1（表示未访问）memset(dist,-1,sizeof(dist));// 读入网格并预处理字母位置for(inti=1;i<=h;i++){for(intj=1;j<=w;j++){cin>>a[i][j];// 如果是小写字母，记录其位置if(islower(a[i][j])){ve[a[i][j]-'a'].push_back({i,j});}}}// BFS求最短路径bfs();// 输出结果if(dist[h][w]==-1){cout<<-1<<endl;// 不可达}else{cout<<dist[h][w]<<endl;// 最短距离}return0;}

【运行结果】

3 4 ..a. #### ba#b 5