2 条题解
-
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; }
信息
- ID
- 525
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 6
- 标签
- 递交数
- 141
- 已通过
- 44
- 上传者