[1,1,0,0,0],
[1,1,0,0,0],
[0,0,0,0,0],
[0,0,0,1,1],
[0,0,0,1,1]
“这是个直观的二维地图,其中1代表有水草的区域,0代表没有水草的区域”。
“可以看到,地图的左上角和右下角各有一大块水草区,称为大区”。
“水草区域可以水平或垂直方向连成大区,但无法对角线连成大区”。
“比如如下就是两块大区”。
[1,0],
[0,1]
“任意给定一个地图,你能找出其中的大区数目吗?”
杨成拿到这个问题,细细地一思考。
这应该和之前的奶牛问题有异曲同工之妙。
先地毯式遍历地图,一旦遇到了水草区域(标记为1的),就从水平,垂直或者说上下左右四个方向搜索相邻的水草区域,这个过程将持续到再也找不到水草区域,是个递归的策略。
每块水草区域一旦被访问过了,就置为0。
一旦当前遍历过程再也找不到水草区域,就算作一个大区,继续地毯式搜索,查找下一块水草区域。