一种思考方式
查看原帖
一种思考方式
556824
hhyyd楼主2022/4/10 17:00

被这个传送门传来传去搞糊涂了,于是想到,传送不耗费时间,传送之后也是要往四个方向走,于是不记录传送门那个点,每次踏进传送门之后,下一步是另外一个门的上下左右就好了。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 310;
char g[N][N];
int n,m,sx,sy;
int dist[N][N];
bool st[N][N];
unordered_map<char,vector<PII>> mp; // 记录传送门位置
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
vector<PII> get_states(int x,int y)
{
    vector<PII> tmp;
    int flag = 0;
    if(g[x][y]>='A'&&g[x][y]<='Z')
    {
        vector<PII> t = mp[g[x][y]];
        int x1 = t[0].first,y1 = t[0].second;
        int x2 = t[1].first,y2 = t[1].second;
        if(x1 == x && y1 ==y)
        {
            x = x2,y = y2;
        }
        else
        {
            x = x1,y=y1;
        }
    }
    for(int i=0;i<4;i++)
    {
        int nx = x+dx[i],ny = y+dy[i];
        tmp.push_back({nx,ny});
    }
    return tmp;
   
}
int bfs(int sx,int sy)
{
    queue<PII> q;
    st[sx][sy] = true;
    q.push({sx,sy});
    dist[sx][sy] = 0;
    while(!q.empty())
    {
        auto t = q.front();
        q.pop();
        int tx = t.first,ty = t.second;
        if(g[tx][ty] == '=') return dist[tx][ty];
        vector<PII> tmp = get_states(tx,ty);
        //cout<<"当前节点: "<<tx<<" "<<ty<<endl;
        for(auto nt : tmp)
        {
            int nx = nt.first,ny = nt.second;
            if(nx < 0 || nx >= n || ny < 0 || ny >= m ) continue;
            if(st[nx][ny] || g[nx][ny] == '#') continue;
            dist[nx][ny] = dist[tx][ty]+1;
            st[nx][ny] = true;
            q.push({nx,ny}); 
        }
    }
    return -1;
}
int main()
{
    cin>>n>>m;
    for (int i = 0; i < n; i ++ )
    {
        for (int j = 0; j < m; j ++ )
        {
            cin>>g[i][j];
            if(g[i][j] == '@') sx = i,sy = j;
            if(g[i][j] >= 'A' && g[i][j] <= 'Z')
            {
                mp[g[i][j]].push_back({i,j});
            }
        }
    }
    int ans = bfs(sx,sy);
    cout<<ans<<endl;
    return 0;
}
2022/4/10 17:00
加载中...