呜呜呜,受不了辣,63分
查看原帖
呜呜呜,受不了辣,63分
573404
该不会是aha吧楼主2022/8/10 09:19
#include<iostream>
#include<algorithm>
#include<cstring>
#include<unordered_map>//用pair做键值会发生错误
#include<map>
#include<queue>//queue是新点后插

#define a first
#define b second

using namespace std;

typedef pair<int,int> PII;

const int N=310;

map<PII,PII> mpos;
map<char,PII> mcp;
bool st[N][N];
int cnt[N][N];//记录走到当前点的步数
char g[N][N];
int app[N];//记录该字符出现次数
int n,m;

int dx[]={0,1,0,-1},dy[]={-1,0,1,0};

int bfs(int sx,int sy,int ex,int ey)
{
    queue<PII> q;
    cnt[sx][sy]=0;
    st[sx][sy]=true;
    q.push({sx,sy});
    
    while(q.size())
    {
        auto t=q.front();
        q.pop();
        
        if(t.a==ex&&t.b==ey) return cnt[ex][ey];
        
        for(int i=0;i<4;i++)
        {
            int x=t.a+dx[i],y=t.b+dy[i];
            if(x>=0&&x<n&&y>=0&&y<m&&!st[x][y]&&g[x][y]!='#')
            {
                cnt[x][y]=cnt[t.a][t.b]+1;
                st[x][y]=true;
                
                
                
                // q.push({x,y});//
                // cout<<"x,y"<<x<<" "<<y<<endl;
                // cout<<"g[x][y]:"<<g[x][y]<<endl;
                
                
                
                if(g[x][y]>='A'&&g[x][y]<='Z')
                {
                    // cout<<app[g[x][y]]<<"+++"<<endl;
                    // cout<<q.front().a<<" "<<q.front().b<<" front"<<endl;
                    
                    if(app[g[x][y]]==1) continue;//若是只有单个门,那么不能通过
                    
                    // cout<<q.front().a<<" "<<q.front().b<<" front"<<endl;
                    
                    if(app[g[x][y]]==2)
                    {
                        int xx=mpos[{x,y}].a,yy=mpos[{x,y}].b;
                        cnt[xx][yy]=cnt[x][y];
                        cnt[x][y]+=2;//碰到传送门,传送过去再回来需要走两步?
                        st[xx][yy]=true;
                        // st[x][y]=false;
                        // memset(st,0,sizeof st);
                        // q.pop();//将传送装置起点弹出队列
                        q.push({xx,yy});
                        q.push({x,y});
                        // break;//因为碰到传送门必须跳
                        
                        // cout<<xx<<" "<<yy<<"***"<<endl;
                    }
                }
                else q.push({x,y});
            }
        }
    }
}

int main()
{
    cin>>n>>m;
    
    int sx,sy,ex,ey;
    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]=='=') ex=i,ey=j;
            if(g[i][j]<='Z'&&g[i][j]>='A')
            {
                int t=g[i][j];
                if(!app[t]) mcp[t]={i,j},app[t]++;
                else
                {
                    mpos[{i,j}]={mcp[t].a,mcp[t].b};
                    mpos[{mcp[t].a,mcp[t].b}]={i,j};
                    app[t]++;
                }
            }
        }
    }
    
    cout<<bfs(sx,sy,ex,ey)<<endl;
    
    // for(int i=0;i<n;i++)
    // {
    //     for(int j=0;j<m;j++)
    //         cout<<cnt[i][j]<<" ";
    //     cout<<endl;    
    // }
    
    // cout<<cnt[ex][ey]<<endl;
    
    return 0;
}
2022/8/10 09:19
加载中...