考察:多源bfs
思路:
模板题.单纯记录证明过程.正解就是将所有值为1的点作为起点.bfs更新到达其他点的距离.
实际上相当于建立一个超级源点.该源点到其他为1的点距离是0.每次bfs取出队头的点一定是离源点距离最近的点.再以此更新到其他点的距离.这种做法很像dijkstra.但是区别是dijkstra入队时距离不一定是最优.但bfs一定是最优的,因为边的距离都为1.队内只存在与超级源点距离为x和x+1的点.每次更新到最新点时,该点被更新的距离一定是最优的,因为队内的距离要么与队头点相等,要么比队头大.所以入队时的距离就是最小的距离.
1 #include <iostream> 2 #include <cstring> 3 #include <queue> 4 using namespace std; 5 typedef pair<int,int> PII; 6 const int N = 1010; 7 char mp[N][N]; 8 int m,n,dist[N][N]; 9 int xx[4] = {-1,1,0,0},yy[4] ={0,0,-1,1}; 10 void bfs() 11 { 12 queue<PII> q; 13 memset(dist,-1,sizeof dist); 14 for(int i=0;i<m;i++) 15 for(int j=0;j<n;j++) 16 if(mp[i][j]==‘1‘) 17 { 18 dist[i][j] = 0; 19 q.push({i,j}); 20 } 21 while(q.size()) 22 { 23 PII it = q.front(); 24 q.pop(); 25 int x =it.first,y = it.second; 26 for(int i=0;i<4;i++) 27 { 28 int dx = x+xx[i],dy = y+yy[i]; 29 if(dx<0||dx>=m||dy<0||dy>=n||dist[dx][dy]!=-1) continue; 30 dist[dx][dy] = dist[x][y]+1; 31 q.push({dx,dy}); 32 } 33 } 34 } 35 int main() 36 { 37 scanf("%d%d",&m,&n); 38 for(int i=0;i<m;i++) 39 scanf("%s",&mp[i]); 40 bfs(); 41 for(int i=0;i<m;i++) 42 for(int j=0;j<n;j++) 43 { 44 printf("%d ",dist[i][j]); 45 if(j+1==n) printf("\n"); 46 } 47 return 0; 48 }