2 条题解

  • 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;
    }
    

    信息

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