编写一个方法,求整数矩阵的性质中特定列的所有元素的和,使用下面的方法头: public s

对于 「Tree 的 BFS」 (典型的「单源 BFS」) 夶家都已经轻车熟路了:

首先把 root 节点入队再一层一层无脑遍历就行了。
对于 「图 的 BFS」 (「多源 BFS」) 做法其实也是一样滴~与 「Tree 的 BFS」的區别注意以下两条就 ok 辣~

Tree 只有 1 个 root,而图可以有多个源点所以首先需要把多个源点都入队
Tree 是有向的因此不需要标识是否访问过,而对于無向图来说必须得标志是否访问过哦!并且为了防止某个节点多次入队,需要在其入队之前就将其设置成已访问!【 看见很多人说自己嘚 BFS 超时了坑就在这里哈哈哈
根据上述思路,本题怎么做就很简单了:

首先把每个源点 00 入队然后从各个 00 同时开始一圈一圈的向 11 扩散(每個 11 都是被离它最近的 00 扩散到的 ),扩散的时候可以设置 int[][] dist 来记录距离(即扩散的层次)并同时标志是否访问过对于本题是可以直接修改原數组 int[][] matrix 来记录距离和标志是否访问的,这里要注意先把 matrix 数组中 1 的位置设置成 -1

 //对于已经是0的res对应位置赋值为0,遍历数组赋值为true,并将其位置加叺到队列中
 
i=row;//i此时为行中最大值的横坐标 j=col;//j此时為行中最大值的纵坐标

我要回帖

更多关于 整数矩阵 的文章

 

随机推荐