菜鸟有一难题求解决!这串逻辑不会实现!

Scaryking 发布于 2016/05/10 12:24
阅读 177
收藏 0

有这么一道题:

    在一个10X10的数组矩阵中划直线,不确定直线的从哪个角度划,也不确定划多少条。求被直线划过后划过后,矩阵被分割出的块数。(假设在矩阵正中间打个X,就被分成四块,就是这么个意思)

提供的算法是这样的,原矩阵全部填0,被划过的地方改为1。从第一行开始遍历,遇到1就做记录,1与1之间的所有0记作一段,有多少段就会分出多少个区域。若第二行的0与第一行的0有交集(打个比方,第一行出现一段是1-3,第二行出现一段是2-7,那就说明有交集),则这两个区域归为一个区域。

求用java实现。

 

我在实现的过程中遇到了一个难题:

    1.标记出每行1的位置,如果第一个位置不是1,当遇到第一个1时则与第一个位置组成一段。

    2.当前行与前一行比较,然后找出交集。

最坑爹的是老板要求一次遍历则全部实现。。。

各位大神有思路或者有实现代码的话恳请赐教,谢谢!

 

 

 

 

 

加载中
0
boystudio
boystudio

若线只有横竖,一次遍历可以实现,假设数组是 arr[0-9][0-9],那么就从第一行开始,检测上边沿和左边沿,若都没有或为0,计数器+1,否则计数器不变,就可以了。

若有斜线,一次遍历也可以实现,但需要区域标志,每个点都要进行九宫格判断,也就是对前后左右斜角都进行判断和标记区块。

返回顶部
顶部