第五十一章 贪吃的河马

第五十一章 贪吃的河马 (第2/2页)

“比如如下就是两块大区”。
　　
　　[1，0]，
　　
　　[0，1]
　　
　　“任意给定一个地图，你能找出其中的大区数目吗？”
　　
　　杨成拿到这个问题，细细地一思考。
　　
　　这应该和之前的奶牛问题有异曲同工之妙。
　　
　　先地毯式遍历地图，一旦遇到了水草区域（标记为1的），就从水平，垂直或者说上下左右四个方向搜索相邻的水草区域，这个过程将持续到再也找不到水草区域，是个递归的策略。
　　
　　每块水草区域一旦被访问过了，就置为0。
　　
　　一旦当前遍历过程再也找不到水草区域，就算作一个大区，继续地毯式搜索，查找下一块水草区域。
　　
　　依据上面的算法，左上角第一块大区被找到后，地图是这样：
　　
　　[0，0，0，0，0]，
　　
　　[0，0，0，0，0]，
　　
　　[0，0，0，0，0]，
　　
　　[0，0，0，1，1]，
　　
　　[0，0，0，1，1]
　　
　　接着右下角第二块大区被访问完后，地图全屏都为0：
　　
　　[0，0，0，0，0]，
　　
　　[0，0，0，0，0]，
　　
　　[0，0，0，0，0]，
　　
　　[0，0，0，0，0]，
　　
　　[0，0，0，0，0]
　　
　　自然而然，大区数目为2块。
　　
　　“伙计，代码这么快就出来了”，科勒文饶有兴趣地盯着编辑器面板。
　　
　　“不过我得好心提醒你，河马每年都会杀死几个有意无意闯入它们地盘的人类”。
　　
　　“所以咋们还是做好撤退的打算吧~”