上海做网站哪家公司好,敬请期待前一句,班级网站建设需求,利为汇网站建设这是一个典型的多源BFS问题#xff0c;如果初学数据结构的同学#xff0c;可能第一次不能想到#xff0c;但是如果做过一次应该就能运用了。 主要思路大概是初始时#xff0c;多个点进入队列然后进行BFS。将某一等价集合视作同一个起始点#xff08;超级源点… 这是一个典型的多源BFS问题如果初学数据结构的同学可能第一次不能想到但是如果做过一次应该就能运用了。 主要思路大概是初始时多个点进入队列然后进行BFS。将某一等价集合视作同一个起始点超级源点先将此源点入队再一层一层向外扩张。相当于这些初始出队的源点在整个问题中地位等价。另外还可以视作不同的起点同时进行BFS操作而不需要依次作为起点依次BFS有时写在一起更方便。
腐烂的橘子 由于这里腐烂的橘子应该是同时向外感染腐烂的如果分不同次进行BFS问题会很棘手但是如果将腐烂的橘子进行多源BFS则最后一层实际上就是最后腐烂的橘子它腐烂的时间就是整个问题的答案。 这里使用tuple存储顶点信息很方便。
class Solution {
public:int orangesRotting(vectorvectorint grid) {queuetupleint,int,int q;int num0;//记录剩余新鲜橘子个数mgrid.size(),ngrid[0].size();for(int i0;im;i)for(int j0;jn;j)if(grid[i][j]2){q.push({i,j,0});//存放腐坏橘子位置以及它腐坏时经过的时间}else if(grid[i][j]) num;int ans-1;while(!q.empty()num){int xget0(q.front());int yget1(q.front());ansget2(q.front()); q.pop();//时间一定为不减序列for(int k0;k4;k){int idx[k],jdy[k];if(check(xi,yj)grid[xi][yj]1){grid[xi][yj]2;q.push(make_tuple(xi,yj,ans1));--num;}}}if(num!0) return -1;return ans1;//ans1是答案的原因是当num0时已经没有腐坏橘子可以更新了会直接break但是此时最外层福坏橘子的ans并未被记录成答案}
private:bool check(int x,int y){if(x0xmy0yn) return true;return false;}int m,n;const int dx[4]{0,1,0,-1};const int dy[4]{-1,0,1,0};
};许久没做图论问题把方向写错了感觉是惯性思维了这里记录下来防止以后又写错。写成了这样
const int dx[4]{0,1,0,-1};
const int dy[4]{-1,0,1,0};
for(int i:dx)//wrong//wrong//wrong//wrong//wrong//wrong//wrongfor(int j:dy){//wrong//wrong//wrong//wrong//wrong//wrong//wrong//巴拉巴拉//wrong}//wrong上述写法方向一共有4*416种其中8个是正常的顶点四周的8个方向左上左左下上下右上右右下对于每一个x方向遍历y8个是无用的重复方向。而实际上方向只有四个dx[i]和dy[i]组合形成一个方向以下是正确方式
const int dx[4]{0,1,0,-1};
const int dy[4]{-1,0,1,0};
for(int k0;k4;k){//正确打开方式遍历四个方向ixdx[k];jydy[k];g[i][j]0;
}
