BFS证明

多源BFS

求矩阵中每个0到最近的1的距离(有很多源点,求到其他点的到每个源点的最短距离)

矩阵距离

1.按距离扩展：距离为0的点、为1、为2、为3...的点。
2.建立虚拟源点,求虚拟源点到其他点的最短距离(Dijkstra)

上图Dijkstra求从虚拟源点到其他点的最短距离,等价于BFS把所有起点放到队列中,进行扩展。

CODE

#include<iostream>
#include<cstring>
using namespace std;

typedef pair<int,int> PII;
const int N = 1010;

#define x first 
#define y second

char g[N][N];
int n,m;
int d[N][N];
PII q[N * N];

void bfs()
{
    memset(d,-1,sizeof d);
    
    int dx[] = {-1,0,1,0}, dy[] = {0,1,0,-1};
    int hh = 0,tt = -1;
    for(int i = 0;i < n;i++)
     for(int j = 0;j < m;j++)
      if(g[i][j] == '1') {
          q[++tt] = {i,j};
          d[i][j] = 0;
      }
    
    while(hh <= tt)
    {
        PII t = q[hh++];
        
        for(int i = 0;i < 4;i++)
        {
            int a = t.x + dx[i],b = t.y + dy[i];
            if(a < 0 || a >= n || b < 0 || b >= m) continue;
            if(d[a][b] != -1) continue;
            
            d[a][b] = d[t.x][t.y] + 1;
            q[++tt] = {a,b};
        }
        
    }
}



int main()
{
    cin>>n>>m;
    for(int i = 0;i < n;i++)
     cin>>g[i];
     
    bfs();
    
    for(int i = 0;i < n;i++)
    {
     for(int j = 0;j < m;j++) cout<<d[i][j]<<' ';
     puts("");
    }
    
    return 0;
}