81分求助
查看原帖
81分求助
668627
buqiming楼主2022/12/12 13:47
#include<iostream>
#include<cstring>
#include<vector>
#define x first
#define y second

using namespace std;

const int N=400;
int a[N][N],v[N][N];//起点:1,终点2,草地3,玉米地4,装置10----
bool st[N][N];
int n,m,sx,sy;
const int dx[]={-1,1,0,0},dy[]={0,0,1,-1};


typedef pair<int,int> PII;
vector<PII> al[N];
PII q[N*N];

int bfs()
{
    int hh=0,tt=-1;
    q[++tt]={sx,sy};
    st[sx][sy]=1;
    
    while(hh<=tt)
    {
        PII t=q[hh++];
        
        if(a[t.x][t.y]==2) 
        {
            return v[t.x][t.y];
        }
        
        for(int i=0;i<4;i++)
        {
            int xx=t.x+dx[i],yy=t.y+dy[i];
            
            if(xx<1 || xx>n || yy<1 || yy>m) continue;
            if(st[xx][yy]) continue;
            if(a[xx][yy]==4) continue;
            
            v[xx][yy]=v[t.x][t.y]+1;
            if(a[xx][yy]>=10)
            {
                PII end;
                for(int j=0;j<2;j++)
                {
                    PII endd=al[a[xx][yy]][j];
                    if(endd.x==xx && endd.y==yy) continue;
                    end.x=al[a[xx][yy]][j].x,end.y=al[a[xx][yy]][j].y;
                    break;
                }

                v[end.x][end.y]=v[xx][yy];
                q[++tt]={end.x,end.y};
            }
            
            else
            {
                st[xx][yy]=1;
                q[++tt]={xx,yy};
            }
        }
    }
}

int main()
{
    cin>>n>>m;
    
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            char aa;
            cin>>aa;
            if(aa=='@') 
            {
                a[i][j]=1;
                sx=i,sy=j;
            }
            else if(aa=='=') a[i][j]=2;
            else if(aa=='.') a[i][j]=3;
            else if(aa=='#') a[i][j]=4;
            else
            {
                a[i][j]=aa-'A'+10;
                al[a[i][j]].push_back({i,j});
            }
        }
    }
    cout<<bfs()<<endl;
}

2022/12/12 13:47
加载中...