宽度优先搜索和深度优先搜索在我看来,他们的区别是宽度优先搜索会优先遍历在当前状态下的所有情况,而深度优先搜索是先将一种方法途径一直走下去直到边界,然后回溯走下一条道路。
一
有一幅以 m x n 的二维整数数组表示的图画 image ,其中 image[i][j] 表示该图画的像素值大小。
你也被给予三个整数 sr , sc 和 newColor 。你应该从像素 image[sr][sc] 开始对图像进行 上色填充 。
为了完成 上色工作 ,从初始像素开始,记录初始坐标的 上下左右四个方向上 像素值与初始坐标相同的相连像素点,接着再记录这四个方向上符合条件的像素点与他们对应 四个方向上 像素值与初始坐标相同的相连像素点,……,重复该过程。将所有有记录的像素点的颜色值改为 newColor 。
最后返回 经过上色渲染后的图像 。
分析
这道题很简单,从初始位置开始走,把为1的走完就可以了,宽搜和深搜都可以做,但是现在存在一个问题,就是要记住我们走过了哪些点,避免进入死循环。因为会更改image的数值,所以可以作为我们的判断标准,但是但是,如果newcolor和原来的值相同,就没不能够直接做了,会死循环,我们发现在这种情况下无需更改,直接返回就好了。
1 深搜
1 | int std=image[sr][sc];//定义相同标准值 |
2 宽搜
1 | int std=image[sr][sc]; |
二
给你一个大小为 m x n 的二进制矩阵 grid 。
岛屿 是由一些相邻的 1 (代表土地) 构成的组合,这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0(代表水)包围着。
岛屿的面积是岛上值为 1 的单元格的数目。
计算并返回 grid 中最大的岛屿面积。如果没有岛屿,则返回面积为 0
分析
先找到一个1,再以他为起点,找出其他与他相邻的1,为了避免在找1的过程中找到了属于同一个岛屿的1,我们可以将之前搜过的岛屿给删掉,就是将其值置为0。
1宽搜
1 | int Max=0; |
2深搜
1 | int dfs(vector<vector<int>>& grid,int y,int x) |
宽度优先搜索要尽量避免将重复的对象入队,以免造成搜索重复,所以在入队的时候就应当将其的状态置为不再可用的状态。
而深度优先搜索因为有回溯的情况发生,所以要根据具体情况去判断,例如在搞全排列的时候,递归出来后就应该将其状态恢复成可用状态。
本文作者: jiangyuhao
本文链接: http://example.com/2022/03/28/%E5%AE%BD%E6%90%9C%E4%B8%8E%E6%B7%B1%E6%90%9C/
版权声明: 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处!