2 条题解
-
1
跑两遍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
上面题解很好了 我来小补充一下吧 唯一注意:最终判定是否都能到达@卡了 不然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
- 上传者