算法分析

多源bfs问题

• 将所有源点加入到队列，求出所有多源起点到所有点的最短距离

注意：由于输出数据过多，Java的同学需要用BufferWriter输出,否则会报错

时间复杂度 $O(n^2)$

参考文献

算法提高课

Java 代码

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main{
    static int N = 1010;
    static int n ;
    static int m ;
    static char[][] g = new char[N][N];
    static int[][] dist = new int[N][N];
    static int[] dx = new int[] {-1,0,1,0};
    static int[] dy = new int[] {0,1,0,-1};
    static void bfs()
    {
        Queue<PIIs> q = new LinkedList<PIIs>();
        for(int i = 0;i < n;i ++) Arrays.fill(dist[i], -1);
        for(int i = 0;i < n;i ++)
            for(int j = 0;j < m;j ++)
            {
                if(g[i][j] == '1')
                {
                    dist[i][j] = 0;
                    q.add(new PIIs(i,j));
                }
            }
        while(!q.isEmpty())
        {
            PIIs t = q.poll();
            for(int i = 0;i < 4;i ++)
            {
                int a = t.x + dx[i];
                int b = t.y + dy[i];
                if(a < 0 || a >= n || b < 0 || b >= m) continue;
                if(dist[a][b] != -1) continue;
                dist[a][b] = dist[t.x][t.y] + 1;
                q.add(new PIIs(a,b));
            }
        }
    }
    public static void main(String[] args) throws IOException {
        Scanner scan = new Scanner(System.in);
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
        n = scan.nextInt();
        m = scan.nextInt();
        for(int i = 0;i < n;i ++)
        {
            char[] charArray = scan.next().toCharArray();
            for(int j = 0;j < m;j ++)
            {
                g[i][j] = charArray[j];
            }
        }
        bfs();
        for(int i = 0;i < n;i ++)
        {
            for(int j = 0;j < m;j ++)
            {
                out.write(dist[i][j] + " ");
            }
            out.write("\n");
        }
        out.flush();
    }
}
class PIIs
{
    public int x;
    public int y;
    public PIIs(int x,int y)
    {
        this.x = x;
        this.y = y;
    }
}