题目大意:有一个n*m的大陆,在大陆上有三个州(1、2、3),现在需要三个州相连,求最少需要修建多少个单元格作为道路。
题记:
首先要了解一下01BFS。bfs可以O(V+E)求解边权全为1的图上的最短路,但是当边权只有0或者1时,可以使用01BFS来快速求解。
01BFS维护一个双端队列,当边权为0时,是利用push_front()放在队头,边权为1时使用push_back()放在队尾。
以每个国家的任意一格为起点,对整张图跑一遍01BFS,就得到了三个国家到所有各自的距离。最后遍历所有各自,找到三个国家与这个格子的距离之和即是答案。
#include<bits/stdc++.h> using namespace std; #define int long long typedef pair<int,int>PII; #define F first #define S second const int N=1005; const int INF=0x3f3f3f3f; char a[N][N]; int dis[][2]={1,0,0,1,-1,0,0,-1}; int n,m; int dist[N][N][4]; deque<PII>q; bool check(int x,int y,int xx){ if(x<1||x>n||y<1||y>m||a[x][y]=='#'||dist[x][y][xx]!=INF) return false; return true; } void bfs(int xx){ for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(a[i][j]==xx+'0'){ dist[i][j][xx]=0; q.push_back(PII(i,j)); //由于放进去的都是边权为0的点,所以放队头队尾都可以 } //将x州的坐标全部放进队列 while(!q.empty()){ PII st=q.front(); q.pop_front(); //从队头拿出一个元素 int x=st.F,y=st.S; for(int i=0;i<4;i++){ int nx=x+dis[i][0]; int ny=y+dis[i][1]; if(check(nx,ny,xx)){ int flag=a[nx][ny]=='.'; //判断当前走到的这个格子是否为某一个州 //两个不同州格子之间边权也为0 dist[nx][ny][xx]=dist[x][y][xx]+flag; if(flag) q.push_back(PII(nx,ny)); else q.push_front(PII(nx,ny)); } } } } signed main(){ cin>>n>>m; for(int i=1;i<=n;i++) cin>>a[i]+1; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) for(int k=1;k<=3;k++) dist[i][j][k]=INF; //初始化三个州到每一格的距离都是无限大 bfs(1); bfs(2); bfs(3); //bfs三个州 int ans=INF; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ int sum=dist[i][j][1]+dist[i][j][2]+dist[i][j][3]; //cout<<sum<<endl; if(a[i][j]=='.')sum-=2; //由于a[i][j]这个点只需要铺一次道路,所以要减去两次 ans=min(ans,sum); } } if(ans==INF) cout<<"-1"<<endl; else cout<<ans<<endl; return 0; }