2 条题解

  • 1
    @ 2026-3-6 10:54:17

    跑两遍bfs,用两个数组d和f分别记录小Y和小M到当前格子所需的时间 跑完之后再遍历一遍地图,到商店时更新答案,注意特判:需要都能够到商店

    #include<bits/stdc++.h>
    using namespace std;
    #define int long long
    int n,m,sx,sy,ex,ey,ans=1e9;
    char a[210][210];
    int d[210][210],f[210][210];//Y和M到当前格子所需要的时间
    int dx[]={-1,1,0,0};
    int dy[]={0,0,1,-1};
    struct grid{
        int x,y;
    };//公式
    void bfs(int x,int y,int b[210][210]){//这里传int的数组会直接改变数组 但是vector需要加&引用
        queue<grid>q;
        q.push({x,y});
        b[x][y]=0;
        while(!q.empty()){
            int tx=q.front().x,ty=q.front().y;
            q.pop();
            for(int i=0;i<4;i++){
                int nx=tx+dx[i],ny=ty+dy[i];
                if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&a[nx][ny]!='#'&&b[nx][ny]==-1){//1.没有越界
                //2.不是障碍#
                //3.没有访问过
                b[nx][ny]=b[tx][ty]+11;//更新时间
                q.push({nx,ny});
                }
            }
        }
    }
    signed main(){
        cin>>n>>m;
        //记录Y和M的坐标的同时初始化时间数组
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                cin>>a[i][j];
                if(a[i][j]=='Y')sx=i,sy=j;
                if(a[i][j]=='M')ex=i,ey=j;
                d[i][j]=-1;
                f[i][j]=-1;
            }
        }
        bfs(sx,sy,d);//Y
        bfs(ex,ey,f);//M
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(a[i][j]=='@'){
                    if(d[i][j]!=-1&&f[i][j]!=-1){//都可以到这个商店就更新答案
                    ans=min(ans,d[i][j]+f[i][j]);
                    }
                    
                }
            }
        }
        cout<<ans;
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    }
    
    • 0
      @ 2026-4-7 19:42:35

      上面题解很好了 我来小补充一下吧 唯一注意:最终判定是否都能到达@卡了 不然40%

      #include<bits/stdc++.h>
      using namespace std;
      #define int long long
      /*  n*m Y.M是俩个人 .可以走 #不可以走 @是目标餐厅 
          问俩人到达同一个目标餐厅的路程之和最小值是多少
        我们可以学习:对于多起点 地图的起点终点我们可以先找到	各自的BFS地方 之后再对比遍历更新 
      */
      #define PII pair<int,int>
      const int N=230;
      int a1[N][N];
      int a2[N][N];
      char g[N][N];
      int n,m;
      int ans=1e9; 
      int dx[]={1,-1,0,0};
      int dy[]={0,0,-1,1};
      bool check(int x,int y)
      {
        if(x<0||x>n-1||y<0||y>m-1) return 0;
        return 1;	
      }
      void bfs(int x,int y,int s[][N])//传二维数组 
      {
        queue<PII> q;
        s[x][y]=0;//起点不再走 
        q.push({x,y});
        while(q.size())
        { 
          auto t=q.front();
      	q.pop();
      	int xx=t.first;
      	int yy=t.second;
      	for(int i=0;i<4;i++)
      	{
      		int nx=xx+dx[i];
      		int ny=yy+dy[i];
      		if(check(nx,ny)&&(s[nx][ny]==0))//不可以走到-1 走过的不走 
      		{
      		  s[nx][ny]=s[xx][yy]+1;
      		  q.push({nx,ny});
      	    }
      	}	
        }	
        return;
      }
      signed main()
      { std::ios::sync_with_stdio(0);
        cin.tie(0),cout.tie(0);
        int x1,y1,x2,y2;
        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]=='#') a1[i][j]=-1,a2[i][j]=-1;//不可走 
         	  	if(g[i][j]=='Y') x1=i,y1=j;
         	  	if(g[i][j]=='M') x2=i,y2=j;
      	 }
         }
         bfs(x1,y1,a1);//求Y到其他所有可以走的点的最短距离
         bfs(x2,y2,a2);
         for(int i=0;i<n;i++) 
         {
         	for(int j=0;j<m;j++)
         	{
         	  if(g[i][j]=='@')
      		 {
      		   int t=a1[i][j]+a2[i][j];
      		   //还要看这个餐厅是不是俩个人都能到达--气死我了
      		   if(a1[i][j]>0&&a2[i][j]>0) 
      		   ans=min(t,ans);	
      		 }	
      	}
         }
         cout<<ans*11<<"\n";
      	return 0;
      }
      
      • 1

      信息

      ID
      525
      时间
      1000ms
      内存
      256MiB
      难度
      6
      标签
      递交数
      141
      已通过
      44
      上传者