题解

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
struct node{//节点
    int x,y,step;
};
char road[500][500];//道路数组（地图）
bool vis[500][500];//标记数组
int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};//方向数组
int n,m,steps=2147483647;
vector<node>gs;//存储传送门
queue<node>q;//广搜路程
int bfs(){//广搜
    q.push({0,0,1});//起点开始
    vis[0][0]=1;
    while(!q.empty()){
        node f=q.front();
        q.pop();
        if(f.x==n-1&&f.y==m-1)return f.step;//终点
        if(road[f.x][f.y]=='$'){//是传送门
            for(auto a:gs){
                if(a.x!=f.x&&a.y!=f.y&&!vis[a.x][a.y]){//传送
                    q.push({a.x,a.y,f.step});
                    vis[a.x][a.y]=1;
                }
            }
        }
        for(int i=0;i<4;i++){
            int nx=f.x+dir[i][0],ny=f.y+dir[i][1];
            if(nx>=0&&nx<n&&ny>=0&&ny<m&&road[nx][ny]!='#'&&!vis[nx][ny]){
                q.push({nx,ny,f.step+1});
                vis[nx][ny]=1;
            }
        }
    }
    return -1;
}
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++)for(int j=0;j<m;j++){
        cin>>road[i][j];
        if(road[i][j]=='$')gs.push_back({i,j,0});//$传送门
        //.道路
        //#墙壁
    }
    cout<<bfs();
    return 0;
}
/*
16 40
@@@..#.#................#...#...........
..@...##...##.#...................#.....
..@..#..........#.......#...............
..@....#.#..........................#...
..@.##....#..............#........#....#
..@@@@@@@@@@@@@@.....#.........#........
...............@..........#........#.#..
......##.......@........................
#.#............@....#...................
...............@...#....................
.....#.....#...@#.....#..#............#.
.......##...#..@....#..............#..#.
.........#.....@...#.........#..........
...#...........@.....##.............#...
......#....#...@..#........#........#...
#...#..........@@@@@@@@@@@@@@@@@@@@@@@@@
55
这是一道困扰了我一年的题目（2024年NOC加码未来赛事复赛T7）
*/