intellij idea下载 Quartz docker安装部署 Spring Cloud RabbitMQ Java中高进阶架构 winforms flash axios swiftui 河南普通话考试 jquery清除子元素 arduino程序 iot系统 html好看的字体样式 centos查看python版本 websocket库 python练习 python中sort函数 python中time java类的继承 java实用教程 java获取当前时间 linux命令行 嵌入式开发教程 opengl编程指南 groupby 联发科p70 彻底删除mysql eclipse中文版下载 系统维护工具 pr视频加速 ps从入门到精通 还原软件哪个好 国都证券官网下载 超级网游助手 kms工具 字体模糊 dll注入器 人物建模教程
当前位置: 首页 > 学习教程  > 编程语言

Acwing---173. 矩阵距离 (Java)_BFS模板

2021/2/13 19:15:12 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

173. 矩阵距离 ①. 题目②. 思路③. 学习点④. 代码实现原题链接 ①. 题目 ②. 思路 BFS是逐层往外扩散, 那么它本身就带有最短路特性,多起点问题,把初始为1的点都加入队列即可,当我们把1都加入队列 与这一块1最近的点j必然会被先…

173. 矩阵距离

  • ①. 题目
  • ②. 思路
  • ③. 学习点
  • ④. 代码实现

原题链接

①. 题目

在这里插入图片描述

②. 思路

  • BFS是逐层往外扩散, 那么它本身就带有最短路特性,多起点问题,把初始为1的点都加入队列即可,当我们把1都加入队列 与这一块1最近的点j必然会被先计算距离,所以可以直接当作最短路而不用考虑其他1到j的可能的最短路距离。将所有的1进行入队列,st数组进行标记是否访问过,1到1的距离就是0,往外扩散新的节点继承上一个节点最短距离+1

③. 学习点

BFS 最短路径

④. 代码实现

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;


public class _173_矩阵最短距离_BFS {
	/*
	 * 	BFS是逐层往外扩散的 
		那么它本身就带有最短路特性
		多起点问题,把初始为1的点都加入队列即可
		当我们把1都加入队列 与这一块1最近的点j必然会被先计算距离 
		所以可以直接当作最短路而不用考虑其他1到j的可能的最短路距离
	 */
	static int arr[][] , m,n;
	static boolean st[][];
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String[] split = br.readLine().split(" ");
		m=Integer.parseInt(split[0]);
		n=Integer.parseInt(split[1]);
		arr=new int[m][n];
		st=new boolean[m][n];
		
		for (int i = 0; i <m; i++) {
			char[] charArray = br.readLine().toCharArray();
			for (int j = 0; j < n; j++) {
				arr[i][j]=charArray[j]-'0';
			}
		}
		bfs();
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				bw.write(arr[i][j]+" ");
			}
			bw.write("\n");
		}
		bw.flush();
		br.close();
		bw.close();
	}
	
	static void bfs() {
		Queue<int[]> queue = new LinkedList<int[]>();
		int[] dx= {-1,1,0,0},dy= {0,0,1,-1};
		 //1.可以看成从1到各个0的点,而不是从0到1,这样的话值为1的点就是起点
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				//将所有的1节点入队列
				if(arr[i][j]==1) {
					//设置访问过
					st[i][j]=true;
					//初始1到1距离为0
					arr[i][j]=0;
					queue.offer(new int[] {i,j});
				}
			}
		}
		
		while(!queue.isEmpty()) {
			int[] poll = queue.poll();
			//一层一层往外搜索
			for (int i = 0; i < 4; i++) {
				int x=poll[0]+dx[i],y=poll[1]+dy[i];
				//边界值判断 是否访问过
				if(x<0||x>=m||y<0||y>=n||st[x][y]==true) {
					continue;
				}
				st[x][y]=true;
				//新的节点加入队列 存储的就是到1的最短距离
				queue.offer(new int[] {x,y});
				//新的节点继承上一个节点最短距离+1
				arr[x][y]=arr[poll[0]][poll[1]]+1;
			}
		}
	}

}

在这里插入图片描述


本文链接: http://www.dtmao.cc/news_show_700294.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?