题目描述
样例
blablabla
算法1
bfs
将所有源点加入队列,然后再进行 bfs
由于输出数据过多,用Java的话需要用 BufferWriter输出,否则无法通过。
时间复杂度
O($n^2$)
参考文献
Java 代码
import java.io.*;
import java.util.*;
class Point{
int x,y;
public Point(int _x,int _y){
x=_x;
y=_y;
}
}
class Main{
private static int n ;
private static int m ;
private static int[][] nums;
private static int[][] dist;
private static Deque<Point> queue ;
private static int[]dx={-1,0,1,0};
private static int[]dy={0,1,0,-1};
private static void bfs(){
while(queue.size()>0){
Point p=queue.poll();
if(p==null){
break;
}
for(int i=0;i<4;i++){
int x=p.x+dx[i];
int y=p.y+dy[i];
if(x>=0&&x<n&&y>=0&&y<m&&dist[x][y]==-1){
dist[x][y]=dist[p.x][p.y]+1;
queue.offer(new Point(x,y));
}
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String [] strs=reader.readLine().split(" ");
n = Integer.parseInt(strs[0]);
m =Integer.parseInt(strs[1]);
nums=new int[n][m];
dist=new int[n][m];
queue=new LinkedList<>();
for(int []d:dist){
Arrays.fill(d,-1);
}
for (int i = 0; i < n; i++){
strs=reader.readLine().split("");
for(int j=0;j<m;j++){
nums[i][j]=Integer.parseInt(strs[j]);
}
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(nums[i][j]==1){
dist[i][j]=0;
queue.offer(new Point(i,j));
}
}
}
bfs();
BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
for(int i = 0;i < n;i ++){
for(int j = 0;j < m;j ++){
out.write(dist[i][j] + " ");
}
out.write("\n");
}
out.flush();
reader.close(); // 记得关闭
}
}