这一个月以来,都在学习平面上的地图搜索,主要涉及到深度优先搜索(DFS)和广度优先搜索(BFS)。这两个算法和相关数据结构我整整学习了一个月,中间经历了很多对自己畏难情绪的克服,现在终于搞懂了,不过并没有掌握得很好。要想掌握得很好,需要后期编码来巩固加强了。

先从这道leetcode上面的题目作为引子:

Number of islands(200)

Given a 2d grid map of ‘1’s (land) and ‘0’s (water), count the number of islands.An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.You may assume all four edges of the grid are all surrounded by water.

   大数据培训,云培训,数据挖掘培训,云计算培训,高端软件开发培训,项目经理培训

  开始看到这道题目时,我的内心是崩溃的。因为我完全是连题目都看不懂,什么是islands?

  islands定义

(1)被water包围;

(2)被水平或者垂直lands相连。

(3)一个只包含0和1的二维数组,找到里面不相邻的只包含1的块的个数。

 

然后看到答案,说解决这道题既可以用到DFS,又可以用到BFS。之前对DFS还有一点点接触,然后BFS就非常头大了。只要遍历一遍,碰到一个1,就把他周围相邻的1都标记为非1,这样整个遍历过程中碰到的1的个数就是所求解。 

 

延伸阅读

学习是年轻人改变自己的最好方式-Java培训,做最负责任的教育,学习改变命运,软件学习,再就业,大学生如何就业,帮大学生找到好工作,lphotoshop培训,电脑培训,电脑维修培训,移动软件开发培训,网站设计培训,网站建设培训学习是年轻人改变自己的最好方式