返回

编程之战

首页
关灯
护眼
字体:
第五十一章 贪吃的河马
   存书签 书架管理 返回目录
 “水草区域可以水平或垂直方向连成大区,但无法对角线连成大区”。

    “比如如下就是两块大区”。

    [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块。

    “伙计,代码这么快就出来了”,科勒文饶有兴趣地盯着编辑器面板。

 

第五十一章 贪吃的河马(2/3)
上一页 目录 下一页