1 条题解

  • 0
    @ 2024-5-4 10:32:05

    思路

    01bfs

    维护 33 个最短距离,d[0][i][j] 表示从外围走到 (i,j)(i,j) 的最短距离,d[1][i][j] 表示从第一个人走到 (i,j)(i,j) 的最短距离,d[2][i][j] 表示从第二个人走到 (i,j)(i,j) 的最短距离,最后 ans=min(d[0][i][j]+d[1][i][j]+d[2][i][j])ans=min(d[0][i][j]+d[1][i][j]+d[2][i][j])

    有两个细节要注意:

    1.如果 s[i][j]='#' ,三段距离重复计算了,需要减掉 2 ,即(d[0][i][j]+d[1][i][j]+d[2][i][j]2)(d[0][i][j]+d[1][i][j]+d[2][i][j]-2) 2. 可以直接从外围拯救这两个人,此时 ans=min(ans,d[0][i][j]+d[0][i][j])ans=min(ans,d[0][i][j]+d[0][i][j])

    课堂演示代码:

    #include<bits/stdc++.h>
    #define y1 yy1   //全局变量不能出现y1
    using namespace std;
    typedef long long ll;
    int h,w,ans;
    string s[105];
    int x1,y1,x2,y2,num,d[3][105][105];
    int dx[4]={0,0,1,-1};
    int dy[4]={1,-1,0,0};
    void bfs1()//从四周走到(i,j)的最短距离 
    {
    	bool v[105][105]={0};
    	deque<pair<int,int> >que;
    	for(int j=0;j<=w+1;j++)
    	{
    		v[0][j]=v[h+1][j]=true;
    		d[0][0][j]=d[0][h+1][j]=0;
    		que.push_back({0,j});
    		que.push_back({h+1,j});
    	}
    	for(int i=1;i<=h;i++)
    	{
    		v[i][0]=v[i][w+1]=true;
    		d[0][i][0]=d[0][i][w+1]=0;
    		que.push_back({i,0});
    		que.push_back({i,w+1});
    	}
    	while(que.size())
    	{
    		int x=que.front().first,y=que.front().second; que.pop_front();
    		for(int i=0;i<4;i++)
    		{
    			int xx=x+dx[i],yy=y+dy[i];
    			if(xx<1||xx>h||yy<1||yy>w)continue;
    			if(s[xx][yy]=='*'||v[xx][yy])continue;
    			if(s[xx][yy]=='.'||s[xx][yy]=='$')
    			{
    				d[0][xx][yy]=d[0][x][y];
    				v[xx][yy]=true;
    				que.push_front({xx,yy});
    			}
    			if(s[xx][yy]=='#')
    			{
    				d[0][xx][yy]=d[0][x][y]+1;
    				v[xx][yy]=true;
    				que.push_back({xx,yy});
    			}
    		}
    	}
    }
    void bfs2(int ss,int tt,int op)  //从(s,t)出发走到(i,j)的最短距离 
    {
    	bool v[105][105]={0};
    	deque<pair<int,int> >que;
    	d[op][ss][tt]=0; v[ss][tt]=true;
    	que.push_back({ss,tt});
    	while(que.size())
    	{
    		int x=que.front().first,y=que.front().second;
    		que.pop_front();
    		for(int i=0;i<4;i++)
    		{
    			int xx=x+dx[i],yy=y+dy[i];
    			if(xx<1||xx>h||yy<1||yy>w)continue;
    			if(s[xx][yy]=='*'||v[xx][yy])continue;
    			
    			if(s[xx][yy]=='.'||s[xx][yy]=='$')
    			{
    				d[op][xx][yy]=d[op][x][y];
    				v[xx][yy]=true;
    				que.push_front({xx,yy});
    			}
    			if(s[xx][yy]=='#')
    			{
    				d[op][xx][yy]=d[op][x][y]+1;
    				v[xx][yy]=true;
    				que.push_back({xx,yy});
    			}
    		}
    		
    	}
    	
    } 
    int main()
    {
    	ios::sync_with_stdio(0);cin.tie(0);
    	cin>>h>>w;
    	for(int i=1;i<=h;i++)
    	{
    		cin>>s[i];
    		s[i]='0'+s[i];
    		for(int j=1;j<=w;j++)
    			if(s[i][j]=='$')
    			{
    				++num;
    				if(num==1)x1=i,y1=j;
    				else x2=i,y2=j;
    			}
    	}
    	memset(d,0x1f,sizeof(d));
    	if(num==1)
    	{
    		bfs1();
    		ans=h*w+1;
    		ans=min(ans,d[0][x1][y1]);
    		if(ans<h*w+1)cout<<ans;
    		else cout<<"impossible";
    	}
    	else
    	{
    		bfs1();
    		bfs2(x1,y1,1);
    		bfs2(x2,y2,2);
    		
    		ans=h*w+1;
    		
    		for(int i=1;i<=h;i++)
    			for(int j=1;j<=w;j++)
    				if(s[i][j]=='.'||s[i][j]=='$')
    					ans=min(ans,d[0][i][j]+d[1][i][j]+d[2][i][j]);
    				else if(s[i][j]=='#')
    					ans=min(ans,d[0][i][j]+d[1][i][j]+d[2][i][j]-2);
    		ans=min(ans,d[0][x1][y1]+d[0][x2][y2]);
    		
    		if(ans<h*w+1)cout<<ans;
    		else cout<<"impossible";
    	}
    	return 0;
    }
    

    信息

    ID
    1414
    时间
    1000ms
    内存
    256MiB
    难度
    4
    标签
    递交数
    219
    已通过
    9
    上传者